RSA public key encryption algorithm was developed by Ron Rivest, Adi Shamirh and LenAdleman at (MIT) in 1977. RSA got its name from the development of its name. RSA is the most influential public key encryption algorithm at present, which can

It has been recommended by ISO as a public key data encryption standard to resist all known cryptographic attacks so far. RSA algorithm is based on a very simple number theory fact: it is very easy to multiply two large prime numbers, but it is extremely difficult to decompose their products at that time, so the products can be made public as encryption keys. Because of the calculation of large numbers, the fastest case of RSA is several times slower than DES, whether it is implemented by software or hardware. Speed has always been RSA's shortcoming. Generally speaking, it is only used to encrypt a small amount of data. The speed of RSA is about 1000 times slower than the symmetric cryptographic algorithm corresponding to the same security level.

basis

Decomposition of large numbers and prime number detection-multiplication of two large prime numbers is easy to realize in calculation, but the calculation of decomposing the product into two large prime number factors is so huge that it is impossible to realize it in practical calculation.

The establishment of 1.RSA cryptosystem;

(1) Choose two different big prime numbers p and q;

(2) Calculate the product n=pq and φ (n) = (p-1) (q-1);

(3) Select a random integer E greater than 1 and less than φ (n) so that GCD (e, φ (n)) =1;

(4) calculate d so that de =1mod φ (n);

(5) for each key k=(n, p, q, d, e), the encryption transformation is defined as Ek(x)=xemodn, and the decryption transformation is Dk(x)=ydmodn, where x, y ∈ Zn;

(6) Take {e, n} as the public key and {p, q, d} as the private key.

2. Example of 2.RSA algorithm:

Let's use two small prime numbers 7 and 17 to build a simple RSA algorithm:

(1) Select two prime numbers, p=7 and q =17;

(2) calculate n = pq = 717 =19, and calculate φ (n) = (p-1) (q-1) = 616 =

(3) choose a random integer e=5, less than φ (n) = 96, and be coprime at 96;

(4) find d so that de= 1mod96 and d.

(5) input plain text m = 19, calculate the 5th power modulus of119, and me =195 = 66 mod 1 19, and send out ciphertext C. Cd = 6677 ≡ 19mod119 to get plaintext19.