A Real Life Example Of Rsa Algorithm Information Technology Essay

1. INTRODUCTION

In cryptography, RSA which stands for Rivest, Shamir and Adleman, is an algorithm for public-key cryptography. They present an encryption method with the property that publicly revealing an encryption key does not thereby reveal the corresponding decryption key. This has two important consequences; the fitst one is couriers or other secure means are not needed to transmit keys, since a message can be enciphered using an encryption key publicly revealed by the intended recipient. Only he can decipher the message, since only he knows the corresponding decryption key. The second one is the message can be signed using a privately held decryption key. Anyone can verify this signature using the corresponding publicly revealed encryption key. Signatures cannot be forged, and a signer cannot later deny the validity of his signature [1].

2. DESCRIPTION OF RSA

2.1 RSA Algorithm:

The RSA algorithm operates by encrypting plaintext in blocks and every plaintext block is an integer between 0 and n-1 for some value n, which leads to a block size ≤log2 (n), where the usual size of n is 1024 bits. According to William Stallings the RSA algorithm is described in brief as follows [2].

RSA Key generation

In order to generate keys select two large prime numbers p and q, where p≠q, and calculate n = p Ã- q; where n is known as a modulus. Then Calculate Ø(n) = (p − 1)(q − 1); where Ø(n) is known as the totient function. Choose an integer e, so that gcd (Ø(n),e) = 1; 1 < e < Ø(n); where e is an exponent. In addition calculate the secret exponent d, so that d≡e-1 (mod Ø(n)), where d is the multiplicative inverse of e in mod Ø(n). Finally compute public key PU = {e, n} and compute private key PR = {d, n}

RSA Encryption

To encrypt a message the sender starts by achieving the recipient’s public key (n, e). Then represents the plaintext message as a positive integer m, where m<n. Further the sender calculates the ciphertext c from the plaintext m, so c=me mod n and finally sender sends the ciphertext c to the recipient.

RSA Decryption

To decrypt a message the receiver uses his private key (n, d) to calculate m= cd mod n and extracts the plaintext from the message representative m.

RSA Authentication

Fig1:Public Key Authentication To implement authentication system, the server first execute public key authentication among clients by signing a distinctive message from the client with its private key and thus creates a digital signature. The signature is then sent back to the client and the client authenticates it with the server’s known public key. To verify the message m the server attaches a digital signature s with the actual message and passes on the pair. The server computes s from m by using server’s private key with the help of this equation: s ≡ mdmod n. Any person who already knows the given public key which is linked with the server can easily authenticate that the message m and its signature s is valid by testing that: m ≡ semod n[3].

2.2 A real life example of RSA Algorithm:

To demonstrate the RSA algorithm select two random large prime numbers p=61 and q=53 and compute n=p*q=61*53=3233. Further calculate totient Ø(n)=(p-1)(q-1)=(61-1)(53-1)=60*52=3120. Then choose e>3120 comprise to 3120, Here I choose e=17, and choose d to satisfy de≡ 1 (mod Ø (n)) = 1 (mod 3120) and d<3120. So the actual value of d=2753.

So according to the computed value:

Public Key PU= {17, 3233} Private Key PR= {2753, 3233}

For example to encrypt m=123, we calculate

Encryption C = Me mod n=12317 mod 3233=855

To decrypt c=855, we calculate

DecryptionDecryption M = Cd mod n= 8552753mod 3233= 123

17

123 mod3233=855

2753

855mod 3233=123

Ciphertext

855

Encryption

PR=2753,3233

Plaintext

123

123

Plaintext

PU =17, 3233

Figure 2: Example of RSA Algorithm

2.3. RSA ALGORITHM ATTACKS

Four possible approaches to attacking the RSA algorithm are as follows:

a. Brute force: This involves trying all possible private keys. The defence against the brute-force approach is to use a large key space. However, because the calculations involved, both in key generation and in encryption/decryption, are complex, the larger the size of the key, the slower the system will run.

b. Mathematical attacks: There are several approaches, all equivalent in effort to factoring the product of two primes. Under the Factoring Problem William Stallings identifies three approaches to attacking RSA mathematically [2]:

Factor n into its two prime factors. This enables calculation of f(n) = (p 1) x (q 1), which, in turn, enables determination of d e1 (mod f(n)).

Determine f(n) directly, without first determining p and q. Again, this enables determination of d e1 (mod f(n)).

Determine d directly, without first determining f(n).

c. Timing attacks: These depend on the running time of the decryption algorithm whereby a snooper can determine a private key by keeping track of how long a computer takes to decipher messages. Although the timing attack is a serious threat, there are simple countermeasures that can be used, including the following [4]:

A simple way to prevent timing attacks, regardless of algorithm, is to ensure that all operations with a given algorithm take the same amount of time by “quantizing” the operations into a fixed time period. This approach is highly dependent on the environment, and may degrade performance, but it requires no modification to the algorithm implementations.

For RSA, one can prevent the attacks by introducing what is called “blinding” into the cryptographic operations, without changing the underlying implementation. This process prevents the attacker from knowing what ciphertext bits are being processed inside the computer and therefore prevents the bit-by-bit analysis essential to the timing attack.

d. Protocol attacks: Protocol attacks exploit weaknesses in the way RSA is being used. Among the better known ones are the attacks that exploit the malleability of RSA.

Many of these attacks can be avoided by using padding. Padding a message within the RSA encryption scheme is done by first off generating a string PS of length k−|M|−2|H|−2 of zeroed bytes. The length of PS may be zero. Then Concatenate Hash(L), PS, a single byte with hexadecimal value 0x01, and the message M to form a data block DB of length k−|H|−1 bytes as DB = Hash(L)||PS||0x01||M. In addition generate a random byte string seed of length |H|. Let dbMask=MGF(seed,k−|H|−1), where MGF is the mask generation function. In practice, a hash function such as SHA-1 is often used as MFG. Let maskedDB =DB⊕dbMask.

Then let seedMask = MGF(maskedDB, |H|) and maskedSeed = seed⊕seedMask.

Concatenate a single byte with hexadecimal value 0x00, maskedSeed and maskedDB to form an encoded message EM of length k bytes as EM = 0x00||maskedSeed||maskedDB.

On the decryption side, the structure of the decrypted message has to be verified. For instance, if there is no byte with hexadecimal value 0x01 to separate PS from M, a decryption error occurred. In any case, returning a decryption error to the potential attacker should not reveal any information about the plaintext [5].

Conclusion

I have looked into the RSA algorithm which is a method for implementing public-key cryptosystems whose security rests in part on the difficulty of factoring large numbers. Looking through operations of the algorithm, possible attacks and the counter measures I can conclude by saying that it permits secure communications to be established without the use of couriers to carry keys, and it also permits one to sign digitized documents.