normal
The RSA system uses two large numbers when generating keys, with their product as an model. This article describes a "multi-RSA system" described in PKCS # 1 V2.1, which can use more than two prime numbers as the model.
The multi-RSA key generating algorithm is as follows: 1. Generate K pixels P1, P2, ..., PK2. Request KPI, i = 1, 2, ..., k3. Seeking Euler function value φ n) = π (pi-1) 4. Select Index E to make GCD (e, φ (n)) = 15. Ask an index D = E-1 mod φ (n) 6. Output public key (e, n) And private key (D, N)
Duplex RSA encryption and decryption algorithm are the same as normal RSA: encryption C = ME mod n decrypts M = CD MOD N
For example, in the triplex RSA system, P1 = 3, P2 = 7, P3 = 13, then n = 3 × 7 × 13 = 273, φ (n) = 2 × 6 × 12 = 144, select E = 5 Introduced D = 29. The public key is obtained (5, 273), the private key is (29, 273). Set the express text is m = 18, then the encryption process is c = me mod n = 185 mod 273 = 135, the decryption process is M = CD mod n = 13529 mod 273 = 18
Obviously, to achieve the same number of key digits (number of times), multiple RSA systems are small than the number of prime numbers needed by the ordinary RSA system. Therefore, the advantages of multiple RSA algorithms are mainly manifested in two aspects: 1. Casual calculation of the generated key can be reduced. 2. Apply a grandson's theorem (China's remaining theorem) to reduce decryption and signature calculation.
On the other hand, the smaller the factor, the easier it is. The data released by the RSA laboratory is displayed, the more the number of digits used, the lower the RSA intensity. The following table lists the operations required to attack 2 to a multi-RSA system (unit: MIPS · year).
Key length
2 prime (ordinary)
3 prime number
4 prime number
5 prime number
512 BITS
2.1 x 106
easy
Very easy
very easy
768 BITS
4.0 x 1011
1.2 x 108
easy
Very easy
1024 BITS
1.4 x 1016
3.0 x 1011
2.1 x 108
easy
1536 BITS
8.2 x 1023
1.8 x 1017
1.9 x 1013
4.2 x 1010
2048 BITS
3.8 x 1030
1.5 x 1022
3.2 x 1017
2.3 x 1014
It can be seen that the multi-RSA system has a practical value. In practical applications, taking ordinary or multi-RSA systems, it should be determined depending on the situation.
[related resources]
l RFC 3447 - PKCS # 1: RSA Cryptography Specifications Version 2.1
L a cost-based security analyysis of symmetric and asymmetric key length
l BHW98 column: http://www.9cbs.net/develop/author/netauthor/bhw98/
First release: 2003-10-24 Last revision: 2003-10-24
