origin
One day, xiao Ming and Xiao Hong are caught uploading a note in class, and their plan to fight Super Mario after school is uncovered. This lets two children be remorseful very much, hence discuss together want to invent a set of secret language. Even if the head teacher caught him, there was no way to decipher the contents of the note.
convention
Smart Xiao Ming soon came up with a cool encryption method, so find xiao Hong, began to introduce his scheme.
Xiao Ming took out a pen and paper and patiently explained to Xiao Hong: “First, we need two prime numbers. For easy calculation, we choose 131313 and 171717.”
“Yes, when I was in fourth grade, my math teacher taught me that a prime number is an integer that has no factors except 111 and itself.”
“What a clever one! Xiao Ming is very gratified, “that teacher must also teach Euler function?”
Little red thought a little, shook his head disappointedly, said: “I have not learned.”
“It doesn’t matter, I tell you briefly.” Xiao Ming comforted Xiao Hong quickly, “We have chosen 131313 and 171717, so let’s work out a n=13×17=221n=13×17=221n=13×17=221. The euler function phi (n) = (13-1) * (17) – 1 = 192 \ varphi (n) = (13-1) * (17-1) = 192 phi (n) = (13-1) * (17) – 1 = 192.”
Red nodded her head vaguely and asked, “What’s the use of this Euler function?”
Xiao Ming drew a circle for the Euler function on the paper. In order to take care of Xiao Hong, he spoke slowly and said, “Next, we need to find a number that is mutually quality with 192192192, and call it eee. This eee is easy to find, let’s just find another prime number, 232323.”
Seeing that Hong did not question, Ming continued: “Let’s find another number DDD, satisfying (de)modφ(n)≡1 (de)\mod\varphi(n)\equiv1(de)modφ(n)≡1, obviously, we can set DDD to 167167167.”
Xiao Hong doesn’t understand the modmodmod operator, so she asks Xiao Ming: “Because 167×23÷192=3841÷192=20… 1167×23÷192=3841÷192=20\cdots\cdots1167×23÷192=3841÷192=20… 1, right?”
‘Yes! As if encouraged by Xiao Hong, Ming said confidently, “Now we have two sets of numbers, which form a key pair, where (e,n)(e,n)(e,n) is the public key and (D,n)(d,n)(d,n) is the private key. I can even ask any of my friends to use the public key to encrypt a message and send it to me. As long as I don’t give away my private key, I’m safe.”
A blush rose on the little red face: “Honeymoon?”
Ming did not seem to find xiao Hong’s abnormality, and continued to work hard. He was not idle: “We agreed that all the information to be delivered in the future will be integer, as our plaintext.”
“Is this really something we kids can learn?” Xiao Hong felt less and less able to see xiao Ming.
encryption
“Is it too difficult? Xiao Ming took out another piece of rough paper and asked with concern.
Although she felt a little bit laboriously, in order to pass the note safely behind, Xiao Hong tried her best to keep up with Xiao Ming’s thinking and said while writing: “When my plaintext is’ hello, ‘I can write (104,101,108,108,111)(104,101,108,108,111)(104,101,108,108,111) using ASCII code. But we’ve tried Morse code before and it’s been cracked by the head teacher. How do we encrypt it this time?”
“Watch me! Ming was glad that Hong could throw a question and continued, “We can use the previously agreed public key (23,221)(23,221)(23,221) to encrypt the five numbers one by one, namely: (10423MOD 221)(104^{23}\ MOD 221)(10423mod221), (10123MOD 221)(101^{23}\ MOD 221)(10123mod221), (10823MOD 221)(108^{23}\ MOD 221)(10823mod221), (10823MOD 221)(108^{23}\ MOD 221)(10823mod221), (11123mod221) (111^{23}\mod 221)(11123mod221), get ciphertext: (26,186,218,218,2)(26,186,218,218,2)(26,186,218,218,2).”
Seeing that a simple ‘hello’ turned into such an undecipherable cipher, Hong smiled with satisfaction and then asked anxiously, “How do I decrypt it? Let’s say I encrypt the message with this public key and send you a ciphertext: (112,111,0)(112,111,0)(112,111,0).”
decryption
“A piece of cake! Unexpectedly, Xiao Hong gave himself a question, Xiao Ming is very excited, writing, “we have agreed in front of a private key (167,221)(167,221)(167,221), that can be calculated before the encryption of the content is: Mod (112167 221) (112 ^ {167} \ mod221) mod221 (112167), (221) 111167 mod (111 ^ {167} \ mod221) mod221 (111167), (221) 0167 mod (0 ^ {167} \ mod221) (0167 mod221), namely (5 0) (0) 5 (5 0). Isn’t that impressive?”
Looking at xiao Ming a face of silly music, completely did not find their overtones, is really in vain their own mental calculation of painstaking, small red look depressed, endure a disappointed mood, low way: “is really a good way, as long as we each prepare a set of key pair, can safely pass the note.”
“Yes, and this experience can be extended to the whole school. It can not only enhance students’ computing ability, but also make the transmission of information more secure. It is really two birds with one stone!” Xiao Ming is very satisfied with his invention.
Hidden trouble
“But…” Xiao Hong was about to speak, but stopped, as if she was worried about destroying Xiao Ming’s mood. She said shyly, “Since I already know that your public key is (E, N)(E, N)(E, N), when the encryption method is known to other students, Inside your private key is known to all of the solving formula of DDD is d = x phi (n) (k + 1) e, k, e, d ∈ (Z) d = \ frac {x (k \ varphi (n) + 1)}} {e, k, e, d ∈ (Z) d = e (k * phi (n) + 1), (k, e, d ∈ Z), Aren’t you afraid of being calculated?”
“That’s a good question! Taking the time to hold his glasses, Ming quickly collected his thoughts and slowly said, “The biggest difficulty here is to calculate φ(n)\varphi(n)φ(n), but to calculate φ(n)\varphi(n)φ(n), we must know which two prime numbers NNN is the product of. Because I’m using this little integer, 221221221, So it’s easy to be prime factorized to figure out 221=13×17221=13×17221=13×17 Phi (221) = (13-1) * (17) – 1 = 192 \ varphi (221) = (13-1) * (17-1) = 192 phi (221) = (13-1) * (17) – 1 = 192, Can try quotient method is used to calculate the d = (20 x 192) + 123 = 167 d = \ frac {(20 x 192) + 1} {23} = 167 d = 23 (20 x 192) + 1 = 167.”
“Then? Why don’t we try big numbers? Harder to calculate?” Xiao Hong seems to have captured the crux of the problem.
“Ok, I’ll try to find two large prime numbers!” Ming shook himself up and began to calculate, “Take two large prime numbers P =49739, Q = 49999P =49739, Q = 49999P =49739, Q = 49999P =49739, Q =49999, N =49739×49999=2486900261n=49739×49999=2486900261n=49739×49999= 2486900261N =49739×49999= 2486900261N =49739×49999= 2486900261N =49739×49999= 2486900261N =49739×49999= 2486900261N =49739×49999=2486900261.
Xiao Hong is still not at ease, worried to ask: “ten thousand class director with computer violence to do?”
Xiao Ming imagined himself as the teacher in charge and began to think about the code algorithm, thinking and saying: “To crack these two prime factors, use trial division, which is 222 to n\ SQRT {n}n, one by one. The time complexity is O(n)O(\ SQRT n)O(n). If I use a large enough prime number, given the current chip speed, it should be safe…”
“That’s right! “We can easily compute the product of two large prime numbers with a computer, but it is very, very difficult to prime factorize the product. In terms of computation time, we have won,” Xiao Hong added.
The ending
Both Ming and Hong were satisfied with the encryption method and decided on the spot their respective key pairs and exchanged their public keys. Then, the two of them hummed a happy ditty, each home, and secretly determined to study hard, as soon as possible to develop a fast prime factorization algorithm for large numbers.
Original link: www.rondochen.com/rsa-manual/