Example illustrating the RSA Demonstration (Indiv. Procedures \ RSA Cryptosystem \ RSA Demonstration)

This text describes an example illustrating the RSA demonstration. The RSA demonstration contains facilities for generating prime numbers and factorising (breaking down into prime factors) natural numbers, plus the RSA Cryptosystem.

To make it easier to follow the steps that need to be performed with CrypTool, the example is illustrated with a number of screenshots. Further information about RSA can be found within the online help pages RSA encryption and dialog box RSA Cryptosystem.

Not only is a description provided of how the RSA algorithm works but the individual steps involved in running the RSA algorithm using small numbers are also described.

This example consists of three parts:

  1. generation of an RSA key,

  2. encryption and decryption of messages and
  3. an attack on the RSA algorithm.

1. Generation of RSA keys

We would like first of all to create an RSA key. To do this, select Individual Procedures \ RSA Cryptosystem \ RSA Demonstration.

dialogrsa-kryptosystem1.gif

For the RSA key, first of all we need two different prime numbers, p and q. You can enter two prime numbers into the fields Prime number p and Prime number q, or you can generate two random prime numbers, p and q.

As an example we wish to generate a random 256-bit RSA key. To this end, click on the Generate prime numbers… button. Similarly to menu selection Indiv. Procedures \ RSA Demonstration \ Generate Prime Numbers…, a dialog box opens in which to generate prime numbers p and q. For prime number p, choose 2^127+2^126 as the lower limit and 2^128 as the upper limit, and activate for the value range the radio button, Both are equal. When you click on Generate prime numbers, two prime numbers p and q of bit length between 127.5 and 128 are generated. When p and q are multiplied together, the result is RSA modulus N of bit length greater than 2*127.5 = 255, i.e. a 256-bit RSA key.

rsaszenariopzgenerieren.gif

You can generate prime numbers as often as you like. If you click on the Apply primes pushbutton, prime numbers p and q are passed to the RSA dialog. At the same time RSA modulus N is calculated, also the Euler phi function phi(N).

The next step is to determine the public RSA key e, a number that is coprime to phi(N). Sometimes it is not easy to find such a number. For this reason we offer a small tip: the number e = 2^16+1 = 65537 (= 10000000000000001 binary) is in practice always coprime to phi(N).

dialogrsa-kryptosystem2.gif

Click on the Update parameters pushbutton, and the secret RSA key d will then be calculated from the number e.

You can now encrypt and decrypt messages.

2. Encryption or decryption of messages using the RSA key pair

Once you have generated the RSA key, you can encrypt and decrypt messages. We will now demonstrate the various options of the RSA algorithm using the samples contained in the script.

Example from Section 4.13.2: encryption of the message ”ATTACK AT DAWN”

First of all generate the RSA key p=47, q=79 e=37. Then click on Update parameters, and the parameters N = p*q = 3713, phi(N) = 3588 and d = 97 are calculated.

Now click on Options for the alphabet and the number system... and activate the Specify alphabet radio button. The predefined alphabet ” ABCDEFGHIJKLMNOPQRSTUVWXYZ” codes the letters <SPACE> as 0, A as 1, ... and Z as 26. Now choose the Number system option in the Method and block length for the coding of text into numbers box and then specify 2 as the block length.

dialogrsaoptions1.gif

To confirm your entries, click on OK. You can now enter the input text, ”ATTACK AT DAWN”, in the input line and click on the Encrypt button.

dialogrsa-kryptosystem3.gif

The encrypted version of this is the number sequence

1404 # 2932 # 3536 # 0001 # 3284 # 2280 # 2235

The number ”#” serves here to visually split up the individual numbers. If you insert these numbers into the input line and then choose Decrypt, the original plaintext will be restored.

dialogrsa-kryptosystem3b.gif

Example from script, section 4.13.3, encryption of the message ”RSA works!”

First of all create the RSA key p=251, q=269 e=65537. Then click on Update parameters, and the parameters N = p*q = 67519, phi(N) = 67000 and d = 2473 are calculated.

  1. Encryption of the message with block length 1
  2. Click on Options for the alphabet and the number system... and activate the radio button All 256 ASCII characters. Now choose the b-adic option in the Method for coding a block into numbers box and then specify 1 as the block length.

    To confirm your entries, click on OK. You can now enter the input text, ”RSA works!”, in the input line and click on the Encrypt button.

    dialogrsa-kryptosystem4.gif

    The encrypted version of this is the number sequence

    58455 # 39103 # 16634 # 28092 # 58597 #

    65768 # 33441 # 20214 # 40199 # 03240

    The number ”#” serves here to visually split up the individual numbers. If you insert these numbers into the input line and then choose Decrypt, the original plaintext will be restored.

  3. Encryption of the message with block length 2
  4. Click on Options for the alphabet and the number system... and activate the radio button All 256 ASCII characters. Now choose the b-adic option in the Method for coding a block into numbers box, and then specify 2 as the maximum block length.

    If you now encrypt the message ”RSA works!”, you will receive a ciphertext that is only half as long:

    03046 # 29337 # 62503 # 09978 # 40883

3. Attack on the RSA algorithm

We illustrate a possible attack on the RSA cryptosystem using already published ”challenges” to crack ciphertexts. As well as the ciphertext, the attacker also has access to the public key e and the RSA modulus N.

The following examples describe attacks for the factorisation of public RSA modulus N. If the factorisation is successful, then all the secret parameters of the RSA cryptosystem can be calculated, and these can then be used to crack the ciphertext challenge. The most well-known crypto challenges are published by RSA Security Lab (www.rsa.com).


Challenge 1 (Stinson)

The challenge unveiled by Professor Stinson in his book [Stinson1995, Exercise 4.6] can also be solved with CrypTool:

Challenge:

The 2 components of the public key:

RSA modulusN = 31313

Public exponente = 4913

Ciphertext:

6340   8309 14010  8936 27358 25023 16481 25809
23614  7135 24996 30590 27570 26486 30388  9395
27584 14999  4517 12146 29421 26439  1606 17881
25774  7647 23901  7372 25774 18436 12056 13547
 7908  8635  2149  1908 22076  7372  8686  1304
 4082 11803  5314   107  7359 22470  7372 22827
15698 30317  4685 14696 30388  8671 29956 15705
 1417 26905 25809 28347 26277  7897 20240 21519
12437  1108 27106 18743 24144 10685 25234 30155
23005  8267  9917  7994  9694  2149 10042 27705
15930 29748  8635 23645 11738 24591 20240 27212
27486  9741  2149 29329  2149  5501 14015 30155
18154 22319 27705 20321 23254 13624  3249  5443
 2149 16975 16087 14600 27705 19386  7325 26277
19554 23614  7553  4734  8091 23973 14015   107
 3183 17347 25234  4595 21498  6360 19837  8463
 6000 31280 29413  2066   369 23204  8425  7792
25973  4477 30989

The formulation of this challenge can also be taken from the CrypTool script [4.13.4 A small RSA cipher challenge (1)].

Cryptanalysis using CrypTool

The analysis is performed in two stages: first of all the prime factorisation of the RSA modulus is calculated using factorisation, and then in the second stage the secret key for encryption of the message is determined. After this, the ciphertext can be decrypted with the cracked secret key.

  1. Factorisation of the RSA modulus with the aid of prime factorisation:
  2. To break down the natural number, select menu sequence Indiv. Procedures \ RSA Cryptosystem \ Factorisation of a Number

    N = 31313 into its prime factors p and q.

    dialogfactorisation1.gif

    It is interesting to see which procedure broke down the RSA modulus the fastest (in this case it is the Brute Force method). Copy the results of factorisation to a text field (mark the output and then use Ctrl+C to copy it to the clipboard).

  3. Calculate the secret key d from the prime factorisation of N and the public key e:
  4. With knowledge of the prime factors p = 173 and q = 181 and the public key e = 4913, you are now in a position to decrypt the ciphertext:

    1. Open the next dialog box via menu selection Indiv. Procedures \ RSA Cryptosystem \ RSA Demonstration:

    2. Enter the prime factors identified, p = 173 and q = 181, and public key e = 4913.

    3. Click on Update parameters. The Euler phi function phi(N) = (p-1)*(q-1) is calculated from the numbers p and q, and from this and public key e the secret RSA key d is determined. Further information will be found in the script, section 4.6.2.

    4. Click on the pushbutton Options for the alphabet and the number system…, and make the following settings:


    5. dialogrsaoptions2.png

    6. Now enter the ciphertext in the input text field. The fastest way to do so is to mark the ciphertext provided above and use Ctrl+C to copy it to the clipboard. Then paste the text into the input field using Ctrl+V.

    7. Now click on the Decrypt button to obtain the plaintext version.


    8. dialogrsa-kryptosystem5.png

The full text of the plaintext goes as follows:

LAKEWOBEGONISMOSTLYPOORSANDYSOILANDEVERYSPRINGTHEEARTHHEAVES
UPANEWCROPOFROCKSPILESOFROCKSTENFEETHIGHINTHECORNERSOFFIELDS
PICKEDBYGENERATIONSOFUSMONUMENTSTOOURINDUSTRYOURANCESTORSCHO
SETHEPLACETIREDFROMTHEIRLONGJOURNEYSADFORHAVINGLEFTTHEMOTHER
LANDBEHINDANDTHISPLACEREMINDEDTHEMOFTHERESOTHEYSETTLEDHEREFO
RGETTINGTHATTHEYHADLEFTTHEREBECAUSETHELANDWASNTSOGOODSOTHENE
WLIFETURNEDOUTTOBEALOTLIKETHEOLDEXCEPTTHEWINTERSAREWORSEZ

The pure solution has been published by Prof. Stinson at http://www.cacr.math.uwaterloo.ca/~dstinson/solns.html


Challenge 2 (Yan)

Using CrypTool, it is possible to solve the challenge presented by Professor Yan in his book [Yan2000, example 3.3.7, page 318]:

Challenge:

The 2 components of the public key:

RSA modulusN = 63978486879527143858831415041;

Public exponente = 17579

Ciphertext:

45411667895024938209259253423,
16597091621432020076311552201,
46468979279750354732637631044,

32870167545903741339819671379

The formulation of this challenge can also be taken from the CrypTool script [4.13.5 A small RSA cipher challenge (2)].

Cryptanalysis using CrypTool

The analysis is performed in two stages: first of all the prime factorisation of the RSA modulus is calculated using factorisation, and then in the second stage the secret key for encryption of the message is determined. After this, the ciphertext can be decrypted with the cracked secret key.

  1. Factorisation of the RSA modulus with the aid of prime factorisation:
    To break down the natural number, select menu sequence Indiv. Procedures \ RSA Cryptosystem \ Factorisation of a Number N = 63978486879527143858831415041 into its prime factors p and q.

    dialogfactorisation2.gif

    It is interesting to see which procedure broke down the RSA modulus the fastest (in this case it is the Quadratic Sieve). Copy the results of factorisation to a text field (mark the output and then use Ctrl+C to copy it to the clipboard).

  2. Calculate the secret key d from the prime factorisation of N and the public key e:

    With knowledge of the prime factors p = 145295143558111 and q = 440334654777631 and the public key e = 17579, you are now in a position to decrypt the ciphertext:

    1. Open the next dialog box via menu selection Indiv. Procedures \ RSA Cryptosystem \ RSA Demonstration:

    2. Enter the prime factors identified, p = 145295143558111 and q = 440334654777631, and public key e = 17579.

    3. Click on Update parameters. The Euler phi function phi(N) = (p-1)*(q-1) is calculated from the numbers p and q by the RSA modulus, and from this and the public key e the secret RSA key d is determined. Further information will be found in the script, section 4.6.2.

    4. Click on the pushbutton Options for the alphabet and the number system…, and make the following settings:

    5. Now enter the ciphertext in the input text field. The fastest way to is to mark the ciphertext provided above and use Ctrl+C to copy it to the clipboard. Then paste the text into the input field using Ctrl+V.

    6. Now click on the Decrypt button to obtain the plaintext version.

Check your results: ”NATURAL NUMBERS ARE MADE BY GOD”.

Remark

You can pass through the two examples above to attack the RSA algorithm also completely from the dialog box RSA Demonstration. So you save the steps to transfer manually the results between the masks.

Start the dialog via Indiv. Procedures \ RSA Cryptosystem \ RSA Demonstration... and then click the 2nd radio button: This means you only know the public parameters. Then click Factorise RSA modulus.

rsaszenariomodulfactorisation.gif