Seonglae ChoRivest-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 MITM
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 패딩은 보안성과 데이터 무결성을 보장하기 위해 메시지를 암호화하거나 서명할 때 추가하는 데이터
& RSA
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.
https://en.wikipedia.org/wiki/RSA_Factoring_Challenge
RSA numbers
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
