How does the RSA algorithm work?
A few days ago, we advertised the public domain name of the RSA algorithm based on equation "C = M ^ e (MOD N)", and today we will explain the RSA algorithm for public domain names through the practice of coding and decoding. How to work. We will use the fictional characters, and we will use some large numbers that are much smaller than the actual use than this algorithm. First, Alice chooses any two Must confidentially 'p' and 'q', (for example, P = 17 and Q = 11). Then she calculates N = P * q, she will get P to get a bigger number with Q. The secret of algorithm lies This number. Decompose a very large number into factors. It is especially difficult. In our example n = 17 * 11 = 187. Alice must choose another number 'E', make E and (P-1) * (Q-1) There is a maximum cent mother (they don't have any 1). For example, E = 7, with '16 * 10 = 160 'does not except for one other than 1, these two numbers' e 'And' n 'will constitute an Alice's public key. Although' E 'may be part of any other person's public key, n should be based on the initial selection factors' P' and 'Q', corresponding to each one. People and different. 'And' n ''s value is the foundation of information encryption, so they should be available to people who want to send encrypted information to Alice. When Alice is published by (E, N) After the public key constituted by = (7187), Bob is able to encode her information. In order to do this, it becomes part of the algorithm, Bob should value the value in the form of numbers. 'Code. One of them is to use the binary value of each character (ASCII), and eventually convert it to decimal. For example, XYZ's ASCII value is 88 (1011000), 89 (1011001) and 90 (1011010) The number of binarys we got is 1011000101001101010, which is 1453274. To simplify this, we will use Z's value, so m = 90. In this way, we have the basic element of the information code: n = 187, e = 7 and m = 90. Now we use the previously mentioned formula "C = M ^ e (MOD N)" = 90 ^ 7 (MOD 187) = 95. In order to get this result, you can use Windows Science Calculator and Some simplified calculations. In this way, C gets the encoding value 95 (c = 95). The model function used is a one-way function, which is not run in reverse. Even if you know the result, it is impossible to calculate Out of M original value. It is the actual meaning that if someone wants to intercept the code information, even if they know the public key of Alice, they can't decode. However, she can export N. She only knows that the value of P and Q can export N. She The private key can be obtained in the following ways: E * D = 1 (MOD (P-1) * (Q-1)) 7 * D = 1 (MOD 160) E * D = 1 (MOD (P-1) * (Q-1)) 7 * D = 1 (MOD 160) uses the Euclides algorithm to calculate D = 23. Once Aiis gets information And have a private key, she can translate it, she can explain the content of the information using the original formula and change the value of the value M = C ^ D (MOD N) to explain the content of the information. In our example (known 23 = 1 2 4 16) This will be: m = 95 ^ 23 (MOD 187) m = [95 ^ 1 (MOD 187) * 95 ^ 2 (MOD 187) * 95 ^ 4 (MOD 187) * 95 ^ 16 (MOD187)] (MOD 187) = [95 * 49 * 157 * 103] (MOD 187) = 75276005 (MOD187) = 90 = z Using ASCII; this information will be sent to Alice.
