11:57 Rsa and primes | |
One day my friend asked me, humanities, why do we need prime numbers, except for fun. The first thing that occurred to me of practical applications, it was RSA.What is RSA?RSA - an acronym that stands for Rivest, Shamir, Adleman. These people have created a cryptographic algorithm, which got its name. Despite the fact that the algorithm was established in 1976, he still remains popular. How does the RSARSA works as follows. Creates two keys - public and private. The private key owner should keep for yourself and to keep secret, open the same can distribute to all comers. Suppose two people want to maintain the confidentiality of correspondence. Let one of them is called Vladimir Putin, and the other Mr President. In this case, there is a third party process - Boris Berezovsky, who was very interesting to read their correspondence. Then BB and DA produce each pair of keys that are exchanged by e-mail public key. BA, with intercepts of each public key, but he, as we shall see later, not much help. Further, BB encrypts the message the public key and sends the second YES encrypted message. BA again, it catches, but can not do anything because to read the key he needed the private key is YES, and YES, in turn, decrypts the received message using its private key, and only he and BB know exactly what is written in this message. The mathematical aspect of the questionFor more inquisitive readers, who consider the algorithm of encryption and decryption. Suppose we have a couple of keys <P, S> (Public - open; Secret - closed). We show how they are formed. Choose two primes p and q. N = p * q T = (p-1) (q-1) Now we choose for E a number with no common prime divisors of T; choose a D that D * E = 1, modulo T. That is, D * E = 1 mod T. mod - means taking the remainder of the modulus T, ie, 5 mod 3 = 3 * 1 + 2 mod 3 = 2. For convenience, I will write mod is not in every computation, but only in those where the mod will be used to make the transition or at the end of the formula to emphasize that we are working in mod N or mod T. Encryption is as follows: the message M is encrypted with a public key P (M) = ME mod N = C (Ciphertext - encrypted message), and the decrypted private key S (C) = CD = (ME) D = ME * D mod N = M1 = M. Now we have to explain the mathematical meaning of these shamanic action. The first logical question - why did it choose two prime numbers, when to do the calculation on the mod can be done without it. The bottom line is that the T is actually worth r(N) - Euler's function, and by its nature, this algorithm proved to be so good. R(n) raises a natural number n in an appropriate amount of numbers relatively prime to it, and not exceeding n. Introduce another concept - ZL. This group of integers, in which mathematical operations are performed in mod L. Why do we choose E prime to T? We do this to the equation E * D = 1 mod T has a solution. Moreover, it is unique. Start up, E is not relatively prime to T and T has a common divisor Q. Then E * X = 1 mod T <=> E * X = A * T + 1 = Q * B, where B - is an integer. But since T is divisible by Q, then 1 is divisible by Q, which is impossible because in ZT 1 * B = 0 <=> B is divisible by T. According to Euler's theorem ar (N) = 1 for all a of ZN. Apply this theorem to our case E * D = 1 mod T <=> E * D = 1 + k (p-1) (q-1), where k - an integer . ME * D = M1 + k (p-1) (q-1) = M * Mk (p-1) (q-1) show that ME * D = M mod p M * Mk (p-1) (q-1) = M * (M (p-1)) k (q-1) mod p = M * (1) k (q-1) = M Here, Euler's theorem lies in the transition M (p-1) = 1 mod p. The attentive reader can easily see that p(p) = p-1 for prime p. Indeed, all the numbers up to p, except for a relatively prime to it. Similarly, ME * D = M mod q. Thus, ME * D = M mod pq So, we have shown that the RSA algorithm is correct. But obviously the same as p, q, D can be chosen by brutforsnym! In fact, the public key is already is a pair E, N. But here again comes into play math - if p and q are large enough numbers, then with the expansion of E on the factors supercomputer will cope for very long. In various articles and books available figures from 100 years until the age of the universe. These numbers depend on the value of p and q. Digital Signaturesgo back to the practical side of the issue. In our example, Boris Abramovich intercepted public key and can send Mr Putin and Dmitry Anatolyevich any obscene writing on behalf of others, such as containing viruses. From the previous section, it is clear that if the public and private keys are interchanged, then the algorithm is essentially unchanged. That is, P (S (M)) = S (P (M)) = M. This idea is based and digital signatures using RSA. The text of M 'is encrypted with the private key and sends the BB and a couple (M', S (M ')) - YES can check this on a couple of matches, and asthma can not slip a pair of DA, because he does not have the private key of explosives. In following posts I plan to talk about the application of RSA in the email client Thunderbird and The Bat, and more to write about the digital signature. | |
|
| |
| Total comments: 0 | |