21 RSA Cryptosystem

LEARNING OBJECTIVES:

• To know about RSA public key crypto system
• To Understand RSA algorithm
• To discuss Security features in RSA

1.1 INTRODUCTION TO RSA:

RSA was first described in 1977 by Ron Rivest, Adi Shamir and Leonard Adleman of the Massachusetts Institute of Technology. Public-key cryptography, also known as asymmetric cryptography, uses two different but mathematically linked keys, one public and one private. The public key can be shared with everyone, whereas the private key must be kept secret. It is based on exponentiation in a finite (Galois) field over integers modulo a prime, using large integers (e.g. 1024 bits). Its security is due to the cost of factoring large numbers.

In RSA cryptography, both the public and the private keys can encrypt a message; the opposite key from the one used to encrypt a message is used to decrypt it. This attribute is one reason why RSA has become the most widely used asymmetric algorithm: It provides a method of assuring the confidentiality, integrity, authenticity and non-reputability of electronic communications and data storage.

RSA signature verification is one of the most commonly performed operations. It derives its security from the difficulty of factoring large integers that are the product of two large prime numbers. Multiplying these two numbers is easy, but determining the original prime numbers from the total factoring is considered infeasible due to the time it would take even using today’s super computers. The public and the private key-generation algorithm is the most complex part of RSA cryptography.

2. RSA ALGORITHM:

The following steps are executed in the RSA algorithm:

1. Bob chooses secret primes p and q and computes n = pq.
2. Bob chooses e with e,(p − 1)(q − 1) = 1.
3. Bob computes d with de ≡ 1 mod(p − 1)(q − 1) .
4. Bob makes n and e public and keeps p, q, d secret.
5. Alice encrypts m as c =m^e (mod n) and sends c to Bob.
6. Bob decrypts by computing m = c^d (mod n).

The security of RSA is based on the belief that the encryption formula (c = m^e mod n ) is a one-way function. The trapdoor that allows Bob to decrypt a Cipher text is the knowledge of factorization n = pq.

2.1 RSA BLOCK DIAGRAM:

2.2 RSA KEY SETUP:

The keys for the RSA algorithm are generated the following way:

•  Choose two distinct prime numbers p and q.
  • For security purposes, the integers p and q should be chosen at random, and should be similar in magnitude but ‘differ in lengthby a few digits’^[2] to make factoring harder. Prime integers can be efficiently found using a primality test.
• Compute n = pq.
  • n is used as the modulus for both the public and private keys. Its length, usually expressed in bits, is the key length.
•  Compute λ(n) = lcm(λ(p), λ(q)) = lcm(p − 1, q − 1), where λ is Carmichael’s totient function. This value is kept private.

• Choose               an       integer e such      that 1      < e < λ(n) and gcd(e, λ(n))    =    1;

  i.e., e and λ(n) are co-prime.

• Determine d as d ≡ e−1 (mod λ(n));                       i.e., d is                 the modular                                                             multiplicativeinverse of e (modulo λ(n)).
• This is more clearly stated as: solve for d given d⋅e ≡ 1 (mod λ(n)).
•  e having a  short bit-length and  small Hamming  weight results

in more efficient encryption – most commonly 216 + 1 = 65,537. However, much smaller values of e (such as 3) have been shown to be less secure in some settings.[13]

•  e is released as the public key exponent.
•  d is kept as the private key exponent.

• The public key consists of the modulus n and the public (or encryption) exponent e. The private key consists of the modulus n and the private (or decryption) exponent d, which must be kept secret. p, q, and λ(n) must also be kept secret because they can be used to calculate d.

KEY GENERATION STEP BY STEP PROCESS WITH EXAMPLE:

Find n and ø(n)

Step 1:

Selecting two large primes at random : p, q (use small numbers for demonstration)

• p = 7;
•  q = 19

Step 2:

Computing their system modulus

• n=p.q                                                  n = 7*19 = 133

ø(n) = (p-1)(q-1)                       ø(n) = (7-1)*(19-1) = 6*18 = 108

Generate Private Key

Step 3:

Selecting at random the encryption key e and gcd (e, 108) = 1. Choose a small number, e co-prime to 108. Using Euclid’s algorithm to find gcd(e,108)

• e = 2 => gcd(e, 108) = 2 ✗
• e = 3 => gcd(e, 108) = 3 ✗
• e = 4 => gcd(e, 108) = 4 ✗
• e = 5 => gcd(e, 108) = 1 ✓

Public Key Generation

Step 4:

Find decryption key d    such that e*d = 1 mod ø(n) and 0≤d≤n e=5; ø(n)=108. Using extended Euclid algorithm;

e*d = 1 mod ø(n) => e*d

= 1+k*ø(n) ; d, k are interger

= (1+k*ø(n))/e

d=(1+k*108)/5

Try through values of k until an integer solution for d is found:

Encryption

Step 5:

Public encryption key: PU={e,n}

• PU = {5,133}
•  For example, Let’s use the message m=16

c = m^e mod n =16⁵

mod 133 =1048576 mod 133

c= 4

Decryption

Step 6:

Secret private decryption key: P_R = {d,n}

• Ø P_R = {65,133}
• Ø From the encryption c=4
• Ø m = c^d mod n

=4⁶⁵mod133

• = 361129467683755×10³⁹ mod 133 m= 16

1.7 RSA ALGORITHM PROCESS   

ENCODE THE ASCII STRING:

Directly computation of exponential needs too much memory and very slow

RSA WHEN DEAL WITH 1024 BITS:

n=93518075472517812751194715143409086574889727146298665297205834 1716028661922905915993804021855830241749312943318773824184453712 0162058121648079083318028014599104077070592823126414272024960940 5749244943892408117844772524625134689327476917023068462758680788 043986062882531909490562722483341876279065122161924203

e=47609

d=11964515064443823593596316031391223220980346742172807039116148 9621549089033006783051907418704947846047912477425584476949894086 4099373984308816603929721452354151974603791286138851972972428882 5143561005547814973195750655549449328508806029373024427172453884 284448045662068755190227462789262813325769121319683889

It could still end up with a number with so many digits (before taking the remainder on dividing by p) that we wouldn’t have enough memory to store it. To avoid this, using Modular Exponential method to enhance computation.

3 MODULAR EXPONENTIAL:

Modular a modulus. It is exponentiation is useful in the field a   type   of exponentiation performed   over of cryptography. The operation of modular exponentiation calculates the remainder when an integer b (the base) raised to the eth power (the exponent), be, is divided by a positive integer m (the modulus).

In symbols, given base b, exponent e, and modulus m, the modular exponentiation c is: c ≡ b^e (mod m).

• Ø Using modular reduction to enhance computation
• Ø f mod i = j and  f = g * h  then
• Ø (( g mod i ) * (h mod i)) mod i = j

FOR EXAMPLE:

• Modular Exponential for 23³⁹¹ mod 55

MODULAR EXPONENTIAL FOR RSA:

The running time of RSA encryption, decryption is simple Algorithm Fast Exponentiation (a, p, n)

Input : Integers a, p, n

Output: r = a^p mod n

if p=0 then

return 1

if p is even then

•  t Fast Exponentiation(a, p/2, n) { p is even, so t= a^p/2 mod n} return t² mod n
•  t Fast Exponentiation(a,(p-1)/2,n) { p is odd, so t= a^(p-1)/2 mod n} return t² mod n

Note that, since the modulo operator is applied after each arithmetic operation, the size of the operands of each multiplication and modulo operation is never more than 2[log2n] bits.

4. SECURITY IN RSA:

The security of RSA relies on the computational difficulty of factoring large integers. As computing power increases and more efficient factoring algorithms are discovered, the ability to factor larger and larger numbers also increases. Encryption strength is directly tied to key size, and doubling key length delivers an exponential increase in strength, although it does impair performance. RSA keys are typically 1024- or 2048-bits long, but experts believe that 1024-bit keys could be broken in the near future, which is why government and industry are moving to

• a minimum key length of 2048-bits.There are two one-way functions involved in the security of RSA

Encryption function: The encryption function is a trapdoor one-way function, whose trapdoor is the private key. The difficulty of reversing this function without the trapdoor knowledge is believed (but not known) to be as difficult as factoring.

Multiplication of two primes :

The difficulty of determining an RSA private key from an RSA public key is known to be equivalent to factoring n. An attacker thus cannot use knowledge of an RSA public key to determine an RSA private key unless they can factor n. Because multiplication of two primes is believed to be a one-way function, determining an RSA private key from an RSA public key is believed to be very difficult.

ANALYZING RSA:

• RSA depends on being able to find large primes quickly, whereas anyone given the product of two large primes “cannot” factor the number in a reasonable time.
• If any one of p, q, m, d is known, then the other values can be calculated. So secrecy is important.
• 1024 bits is considered in risk.
• To protect the encryption, the minimum number of bits in n should be
• RSA is slow in practice
• RSA is primary used to encrypt the session key used for secret key encryption (message integrity) or the message’s hash value (digital signature).

SUMMARY

We have discussed about RSA public key cryptosystem, Key generation using RSA algorithm and Security features of RSA.