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:
We would like first of all to create an RSA key. To do this, select Individual Procedures \ RSA Cryptosystem \ RSA Demonstration.
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.
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).
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.
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.
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.
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.
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.
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.
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.
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.
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).
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:
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.
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.