RSA

Creator

Creator

Seonglae Cho

Created

Created

2020 Mar 28 16:42

Editor

Editor

Seonglae Cho

Edited

Edited

2024 May 29 16:23

Refs

Refs

Diffie-Hellman key exchange

Discrete Logarithm

Rivest-Shamis-Adleman

1977 Ron Rivest, Adi Shamir, and Leonard Adleman created RSA, a general public-key cryptosystem. Clifford Cocks (James’ colleague) implemented RSA

It relies on factors and large prime numbers.

RSA Key generation

Choose two large distinct prime numbers p and q

Compute N = p * q

Given N, hard to factor p and q

For any a, N, and e, with 0 < a < N and e > 1, calculating () = c is easy

Given c, e, and N, hard to calculate

Compute T = (p – 1)(q – 1). This is called the
Euler Totient.

Choose e and d where (e * d) mod T = 1 (
Primitive Root)

Choose e such that e is a prime number, and e does not divide T
Choose d. (using
Extended Euclidean algorithm)

P = (e, N)

S = (d, N)

Example

Choose p=2 and q=7

N = 2 * 7 = 14

T = (p-1)(q-1) = 6

Choose (e * d) mod 6 = 1

e=5, d=11

Public key is (5, 14)

Private key is (11, 14)

RSA Encryption

Public key is (5, 14)

Let's encrypt a message "B".

Let's use encoding A=1, B=2, C=3

Encryption value: 2^5 mod 14 = 4

Encrypted message is "D"

RSA Decryption

Private key is (11, 14)

Let's decrypt "D"

Decrypted value: 4^11 mod 14 = 2

2 is "B", the original value before encryption

RSA Encryption & Decryption

Alice sends a message M to Bob

Must have public key of Bob, = ()

Turn M into an integer m,

Alice: () -> c

Bob: () -> M

Eve: c, and

Insufficient to decrypt c for

Digital Signature

Public key와 Private key가 수학적으로 대칭이기에 encryption decryption 반대로 사용되도 동일하기 때문에 Digital signing에도 가능한 것

메시지 준비:

Alice가 Bob에게 메시지 M을 보낼 때, Alice는 먼저 M을 해싱하여 해시 값 h를 생성합니다. 해싱은 메시지의 길이와 상관없이 일정한 길이의 요약을 만들어냅니다.

서명 생성:

Alice는 자신의 개인 키 dN을 사용하여 해시 값 h를 암호화합니다. 이 과정에서 생성된 값 S가 서명입니다:

이 서명 S는 메시지 M과 함께 Bob에게 전송됩니다.

서명 검증:

Bob이 메시지와 서명을 받으면, 먼저 같은 해시 함수를 사용하여 메시지 M으로부터 해시 값을 h′ 생성합니다.

Bob은 Alice의 공개 키 eN를 사용하여 서명 S를 복호화합니다:

복호화된 해시 값 h가 Bob이 직접 생성한 해시 값 h′와 일치하면, 메시지가 Alice에 의해 서명되었으며 중간에 변경되지 않았음을 확인할 수 있습니다.

How does it works?

From Fermat’s little theorem, you can derive if

RSA Padding

RSA 패딩은 보안성과 데이터 무결성을 보장하기 위해 메시지를 암호화하거나 서명할 때 추가하는 데이터

Fermat’s little theorem & RSA

inst.eecs.berkeley.edu

https://inst.eecs.berkeley.edu/~cs70/fa16/static/slides/lec-12.pdf

Challenges

RSA Factoring Challenge

The RSA Factoring Challenge was a challenge put forward by RSA Laboratories on March 18, 1991[1] to encourage research into computational number theory and the practical difficulty of factoring large integers and cracking RSA keys used in cryptography. They published a list of semiprimes (numbers with exactly two prime factors) known as the RSA numbers, with a cash prize for the successful factorization of some of them. The smallest of them, a 100-decimal digit number called RSA-100 was factored by April 1, 1991. Many of the bigger numbers have still not been factored and are expected to remain unfactored for quite some time, however advances in quantum computers make this prediction uncertain due to Shor's algorithm.

RSA Factoring Challenge

https://en.wikipedia.org/wiki/RSA_Factoring_Challenge

In mathematics, the RSA numbers are a set of large semiprimes (numbers with exactly two prime factors) that were part of the RSA Factoring Challenge. The challenge was to find the prime factors of each number. It was created by RSA Laboratories in March 1991 to encourage research into computational number theory and the practical difficulty of factoring large integers. The challenge was ended in 2007.[1]

https://en.wikipedia.org/wiki/RSA_numbers

Quantum computer

그래서 양자컴퓨터는 왜 빠른 걸까?

최근 이석배 퀀텀에너지연구소 대표 등 다수의 연구진들의 상온 초전도체 관련 논문으로 전세계가 발칵 뒤집혔죠! 초전도체는 양자컴퓨터에 아주 핵심적인 요소라고 할 수 있습니다. ...근데 양자컴퓨터는 뭐길래 세상이 바뀔정도의 영향력이 있다고 하는 걸까요? 도데체 얼마나 빠르고 강력하길래? 사실 양자컴퓨터가 본격적으로 활성화 된다면, 가장 먼저 걱정해야 할 부분이 바로 보안문제 입니다. 양자컴퓨터에 대해 알아보고, 양자컴퓨터로 인해 발생할 보안문제에 대해서도 함께 살펴보죠! #양자컴퓨터 #초전도체 ▀▀▀ A huge thank you to those who helped us understand this complex field and ensure we told this story accurately - Dr. Lorenz Panny, Prof. Serge Fehr, Dr. Dustin Moody, Prof. Benne de Weger, Prof. Tanja Lange, PhD candidate Jelle Vos, Gorjan Alagic, and Jack Hidary. A huge thanks to those who helped us with the math behind Shor’s algorithm - Prof. David Elkouss, Javier Pagan Lacambra, Marc Serra Peralta, and Daniel Bedialauneta Rodriguez. ▀▀▀ References: Joseph, D., et al. (2022). Transitioning organizations to post-quantum cryptography. Nature, 605(7909), 237-243. - https://ve42.co/Joseph2022 Bernstein, D. J., & Lange, T. (2017). Post-quantum cryptography. Nature, 549(7671), 188-194. - https://ve42.co/Bernstein2017 An Insight, An Idea with Sundar Pichai - Quantum Computing, Wold Economic Forum via YouTube - https://ve42.co/QCWEFyt Migrating to Post-Quantum Cryptography, The White House - https://ve42.co/PQCWhiteHouse Kotas, W. A. (2000). A brief history of cryptography. University of Tennessee - https://ve42.co/Kotas2000 Hellman, M. (1976). New directions in cryptography. IEEE transactions on Information Theory, 22(6), 644-654. - https://ve42.co/Hellman1976 Rivest, R. L., Shamir, A., & Adleman, L. (1978). A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2), 120-126. - https://ve42.co/Rivest1978 Kak, A. (2023). Lecture 12: Public-Key Cryptography and the RSA Algorithm - https://ve42.co/Kak2023 Calderbank, M. (2007). The RSA Cryptosystem: History, Algorithm, Primes. University of Chicago. - https://ve42.co/Calderbank2007 Cryptographic Key Length Recommendation, Keylength - https://ve42.co/KeyLength Coppersmith, D. (2002). An approximate Fourier transform useful in quantum factoring. arXiv preprint quant-ph/0201067. - https://ve42.co/Coppersmith2002 Quantum Fourier Transform, Qiskit - https://ve42.co/Qiskit Shor, P. W. (1994, November). Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings 35th annual symposium on foundations of computer science (pp. 124-134). IEEE. - https://ve42.co/Shor1994 Shor’s algorithm, Wikipedia - https://ve42.co/ShorWiki Euler’s totient function, Wikipedia - https://ve42.co/EulerWiki Asfaw, A. (2020). Shor’s Algorithm Lecture Series, Qiskit Summer School - https://ve42.co/ShorYT How Quantum Computers Break Encryption, minutephysics via YouTube - https://ve42.co/PQCmpyt Breaking RSA Encryption - an Update on the State-of-the-Art, QuintessenceLabs - https://ve42.co/QuintessenceLabs O'Gorman, J., & Campbell, E. T. (2017). Quantum computation with realistic magic-state factories. Physical Review A, 95(3), 032338. - https://ve42.co/OGorman2017 Gidney, C., & Ekerå, M. (2021). How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits. Quantum, 5, 433. - https://ve42.co/Gidney2021 2021 Quantum Threat Timeline Report, Global Risk Institute - https://ve42.co/QuantumRisk The IBM Quantum Development Roadmap, IBM - https://ve42.co/IBMQC Post-Quantum Cryptography, Computer Security Resource Center (NIST) - https://ve42.co/CSRCPQC Alagic, G., et al. (2022). Status report on the third round of the NIST post-quantum cryptography standardization process. US Department of Commerce, NIST. - https://ve42.co/Alagic2022 Thijs, L. (2015). Lattice cryptography and lattice cryptanalysis - https://ve42.co/Thijs2015 ▀▀▀ Special thanks to our Patreon supporters: Tj Steyn, Meg Noah, Bernard McGee, KeyWestr, Elliot Miller, Jerome Barakos, M.D., Amadeo Bee, TTST, Balkrishna Heroor, Chris LaClair, John H. Austin, Jr., Eric Sexton, john kiehl, Anton Ragin, Diffbot, Gnare, Dave Kircher, Burt Humburg, Blake Byers, Evgeny Skvortsov, Meekay, Bill Linder, Paul Peijzel, Josh Hibschman, Mac Malkawi, Juan Benet, Ubiquity Ventures, Richard Sundvall, Lee Redden, Stephen Wilcox, Marinus Kuivenhoven, Michael Krugman, Cy 'kkm' K'Nelson, Sam Lutfi. ▀▀▀ Written by Casper Mebius & Derek Muller Edited by Trenton Oliver Filmed by Raquel Nuno Animated by Ivy Tello & Mike Radjabov Additional video/photos supplied by Getty Images & Pond5 Music from Epidemic Sound & Jonny Hyman Produced by Derek Muller, Petr Lebedev, & Emily Zhang Dubbed by Mingi Kwon Additional Edited by JH, J Supported by Yuna Lee

그래서 양자컴퓨터는 왜 빠른 걸까?

https://www.youtube.com/watch?v=qV3k-bQgmK0

그래서 양자컴퓨터는 왜 빠른 걸까?

Recommendations

///////