RSA encryption algorithm, or they are afraid the feds America
Today I want to tell you about an excellent encryption algorithm RSA. The idea to write the message appears in the writing of code encryption botnet. The solution is technology that the U.S. government at the time were very much afraid. Even banned a program, on some lines written on Perl'e, and the people to protest, printed on T-shirts the code of this program.
So a little history:
RSA (alphabetic abbreviation of the names Rivest, Shamir and Adleman) - a cryptographic public key algorithm. RSA algorithm is the first of a type suitable for both encryption and digital signatures. The algorithm is used in a large number of cryptographic applications. published in November 1976 article Whitfield Diffie and Martin Hellman, "New Directions in Cryptography" turned the idea of cryptographic systems, laying the foundations of public key cryptography. Subsequently developed Diffie-Hellman-Merkle allows two parties to get a shared secret key over an insecure channel. However, this algorithm did not solve the problem of authentication. Without additional funds, one of the users could not be sure that he exchanged with the key of the user, which he needed. After reading this article, three scientists Ronald Rivest (Ronald Linn Rivest), Adi Shamir (Adi Shamir) and Leonard Adleman ( Leonard Adleman) from the Massachusetts Institute of Technology (MIT) have begun the search for a mathematical function that would allow you to implement formulated Whitfield Diffie and Martin Hellman model of a cryptographic system with a public key. After working on more than 40 possible variants, they managed to find an algorithm based on the difference in how easy to find large prime numbers and the difficulty lay factoring the product of two large prime numbers, which later received the name of the RSA. The system was named for the first letters of the names of its creators. Description RSA was published in August 1977 in the journal Scientific American. RSA authors supported the idea of its active distribution. In turn, the National Security Agency (USA), for fear of using this algorithm in the state structures, for several years unsuccessfully called for halting the spread of the system. The situation sometimes reaches the point of absurdity - for example, when a programmer Adam Beck (Adam Back) described in Perl algorithm RSA, consisting of five lines, the U.S. government banned the distribution of this program outside the country. People are dissatisfied with such restrictions, in protest of the printed text of the program on their shirts. In 1977, the creators of RSA was encrypted phrase «The Magic Words are Squeamish Ossifrage» («The magic words - is squeamish vulture"). For decoding was promised a reward of $ 100. Only at the end of 1995 could practically implement disclosure RSA cipher for a 500-character key. For six months, more than 600 volunteers donate CPU 1600 machines (two of which were fax machines). Coordination took place through the Internet, and it was one of the first such distributed computing projects. This award winners donated to the Free Software Foundation. in December 1997 has been published information according to which British mathematician Clifford Cox (Clifford Cocks), who worked in the Government Communications Headquarters (GCHQ) UK, described a similar RSA cryptosystem in 1973.
A Little about encryption : - Depending on the structure of the keys used encryption methods are divided into:
Symmetric encryption: outsiders can be known encryption algorithm, but a small portion is unknown classified information - the key is the same for the sender and the receiver of the message;
Examples: DES, 3DES, AES, Blowfish, twofish. asymmetric-encryption: outsiders may know the encryption algorithm, and possibly the public key, but do not know the private key known only to the recipient. Cryptographic system with a public key is now widely used in a variety of network protocols, such as the protocols TLS and its predecessor SSL (underlying HTTPS), as well as SSH, PGP, S / MIME, etc.
The Russian standard, using asymmetric encryption. Currently asymmetric cryptography based on public key RSA (stands for Rivest, Shamir and Aldeman - creators of the algorithm) uses most of the products on the security market. cryptographic It is based on the complexity of factoring large numbers - namely, to exceptionally difficult task to determine the private key on the basis of open, since this would require to solve the problem of the existence of divisors of an integer. Most systems use a cryptographically strong 1024-bit and big numbers.
Consider RSA algorithm from a practical point of view.
First we need to generate a public and private key: -Take two large prime numbers P and q. define-n, by multiplying P on q (n = P * q). -We choose a random number, which we call d. This number must be prime to the product of (p-1) * (q-1). - We define a number e, for which the following relation is true (e * d) mod ((p-1) * (q- 1)) = 1. Hazovem-public key of e and n, and the secret - d and n.
__________________________________________________________________________________
To encrypt data on the public key {e, n}, you will need: -encrypted text divided into blocks, each of which can be expressed as the number of M (i) = 0,1,2 ..., n-1 (ie, only up to n-1). cipher-text, considered as a sequence of numbers M (i) by the formula C (i) = (M (I) ^ e) mod n. To decrypt the data using the private key {d, n}, do the following calculation: M (i) = (C (i) ^ d) mod n. As a result, you receive a set of numbers M (i), which are the source code. _________________________________________________________________________________
The following example illustrates the encryption algorithm RSA: encrypts and decrypt the message "CAB" algorithm RSA. For simplicity we take small numbers - it will reduce our calculations. We choose p = 3 and q = 11. We define n = 3 * 11 = 33. Haydem-(p-1) * (q-1) = 20. Therefore, d is equal to, say, 3: (d = 3). , choose a number e as follows: (e * 3) mod 20 = 1. So e will be the same, for example, 7: (e = 7). represent-key encrypted message as a sequence of numbers in the range from 0 to 32 (Unforgettable, that ends at n-1). The letter A = 1, B = 2, C = 3. now encrypts the message using the public key {7.33} C1 = (3 ^ 7) mod 33 = 2187 mod 33 = 9; C2 = (1 ^ 7) mod 33 = 1 mod 33 = 1; C3 = (2 ^ 7) mod 33 = 128 mod 33 = 29; Now decrypt data using a private key {3.33}. M1 = (9 ^ 3) mod 33 = 729 mod 33 = 3 (C); M2 = (1 ^ 3) mod 33 = 1 mod 33 = 1 (A); M3 = (29 ^ 3) mod 33 = 24 389 mod 33 = 2 (B), data decrypted! And so it acts this algorithm RSA! The article, though not big, but useful, and brings valuable information for both novice and experienced programmers.
Thanks,
RSA (alphabetic abbreviation of the names Rivest, Shamir and Adleman) - a cryptographic public key algorithm. RSA algorithm is the first of a type suitable for both encryption and digital signatures. The algorithm is used in a large number of cryptographic applications. published in November 1976 article Whitfield Diffie and Martin Hellman, "New Directions in Cryptography" turned the idea of cryptographic systems, laying the foundations of public key cryptography. Subsequently developed Diffie-Hellman-Merkle allows two parties to get a shared secret key over an insecure channel. However, this algorithm did not solve the problem of authentication. Without additional funds, one of the users could not be sure that he exchanged with the key of the user, which he needed. After reading this article, three scientists Ronald Rivest (Ronald Linn Rivest), Adi Shamir (Adi Shamir) and Leonard Adleman ( Leonard Adleman) from the Massachusetts Institute of Technology (MIT) have begun the search for a mathematical function that would allow you to implement formulated Whitfield Diffie and Martin Hellman model of a cryptographic system with a public key. After working on more than 40 possible variants, they managed to find an algorithm based on the difference in how easy to find large prime numbers and the difficulty lay factoring the product of two large prime numbers, which later received the name of the RSA. The system was named for the first letters of the names of its creators. Description RSA was published in August 1977 in the journal Scientific American. RSA authors supported the idea of its active distribution. In turn, the National Security Agency (USA), for fear of using this algorithm in the state structures, for several years unsuccessfully called for halting the spread of the system. The situation sometimes reaches the point of absurdity - for example, when a programmer Adam Beck (Adam Back) described in Perl algorithm RSA, consisting of five lines, the U.S. government banned the distribution of this program outside the country. People are dissatisfied with such restrictions, in protest of the printed text of the program on their shirts. In 1977, the creators of RSA was encrypted phrase «The Magic Words are Squeamish Ossifrage» («The magic words - is squeamish vulture"). For decoding was promised a reward of $ 100. Only at the end of 1995 could practically implement disclosure RSA cipher for a 500-character key. For six months, more than 600 volunteers donate CPU 1600 machines (two of which were fax machines). Coordination took place through the Internet, and it was one of the first such distributed computing projects. This award winners donated to the Free Software Foundation. in December 1997 has been published information according to which British mathematician Clifford Cox (Clifford Cocks), who worked in the Government Communications Headquarters (GCHQ) UK, described a similar RSA cryptosystem in 1973.
A Little about encryption : - Depending on the structure of the keys used encryption methods are divided into:
Symmetric encryption: outsiders can be known encryption algorithm, but a small portion is unknown classified information - the key is the same for the sender and the receiver of the message;
Examples: DES, 3DES, AES, Blowfish, twofish. asymmetric-encryption: outsiders may know the encryption algorithm, and possibly the public key, but do not know the private key known only to the recipient. Cryptographic system with a public key is now widely used in a variety of network protocols, such as the protocols TLS and its predecessor SSL (underlying HTTPS), as well as SSH, PGP, S / MIME, etc. The Russian standard, using asymmetric encryption. Currently asymmetric cryptography based on public key RSA (stands for Rivest, Shamir and Aldeman - creators of the algorithm) uses most of the products on the security market. cryptographic It is based on the complexity of factoring large numbers - namely, to exceptionally difficult task to determine the private key on the basis of open, since this would require to solve the problem of the existence of divisors of an integer. Most systems use a cryptographically strong 1024-bit and big numbers.
Consider RSA algorithm from a practical point of view.
First we need to generate a public and private key: -Take two large prime numbers P and q. define-n, by multiplying P on q (n = P * q). -We choose a random number, which we call d. This number must be prime to the product of (p-1) * (q-1). - We define a number e, for which the following relation is true (e * d) mod ((p-1) * (q- 1)) = 1. Hazovem-public key of e and n, and the secret - d and n.
__________________________________________________________________________________
To encrypt data on the public key {e, n}, you will need: -encrypted text divided into blocks, each of which can be expressed as the number of M (i) = 0,1,2 ..., n-1 (ie, only up to n-1). cipher-text, considered as a sequence of numbers M (i) by the formula C (i) = (M (I) ^ e) mod n. To decrypt the data using the private key {d, n}, do the following calculation: M (i) = (C (i) ^ d) mod n. As a result, you receive a set of numbers M (i), which are the source code. _________________________________________________________________________________
The following example illustrates the encryption algorithm RSA: encrypts and decrypt the message "CAB" algorithm RSA. For simplicity we take small numbers - it will reduce our calculations. We choose p = 3 and q = 11. We define n = 3 * 11 = 33. Haydem-(p-1) * (q-1) = 20. Therefore, d is equal to, say, 3: (d = 3). , choose a number e as follows: (e * 3) mod 20 = 1. So e will be the same, for example, 7: (e = 7). represent-key encrypted message as a sequence of numbers in the range from 0 to 32 (Unforgettable, that ends at n-1). The letter A = 1, B = 2, C = 3. now encrypts the message using the public key {7.33} C1 = (3 ^ 7) mod 33 = 2187 mod 33 = 9; C2 = (1 ^ 7) mod 33 = 1 mod 33 = 1; C3 = (2 ^ 7) mod 33 = 128 mod 33 = 29; Now decrypt data using a private key {3.33}. M1 = (9 ^ 3) mod 33 = 729 mod 33 = 3 (C); M2 = (1 ^ 3) mod 33 = 1 mod 33 = 1 (A); M3 = (29 ^ 3) mod 33 = 24 389 mod 33 = 2 (B), data decrypted! And so it acts this algorithm RSA! The article, though not big, but useful, and brings valuable information for both novice and experienced programmers.
Thanks,
