RSA Visualization Tools Download Page

RSA Visualization Tools Download Page

This page has three versions of our RSA Visualization prototype software for Windows, Linux and MacOS.

Installation

Run RSAVisual from the installation directory. A window shows up in which the following "pages" are available.

User Guide

RSA Page (Demo mode)

This page shows an instance of RSA encryption and decryption.

To change the value of a number, enter a new value in the corresponding line edit and press return key to confirm modification. The numbers could be changed are the two prime numbers p and q, public key e, and text to encrypt m. Other numbers are computed automatically and not manually editable.

To generate a new random instance, press "New Instance".

To practice the calculation, press "Practice".

RSA Page (Practice mode)

This page allows you to practice the calculation of RSA encryption with relatively small numbers. Given the two prime numbers p and q, public key e, and text to encrypt m, you need to calculate the value of n, φ(n), the private key d, and ciphertext c.

To show the hint for each question, press "Hint", so that the equation will be displayed. To show the answer for each question, press "Ans", so that the answer will be automatically filled in.

To switch back to the demonstration mode, press "Demo".

E. Euclidean Page

This page shows the use of Extended Euclidean Algorithm to calculate the private key d, given public key e and φ(n). Colors in table cells reveal the relationship among cells. Two cells in adjacent rows with the same color and value indicates that the number in the lower cell comes from the upper cell. The x value in the last line is the private key.

The extended Euclidean algorithm not only computes the greatest common divisor gcd(a,b) of two input integers a, b, but also computes two integers x and y that fulfill the relationship of ax+by=gcd(a,b). Filling this table consists of two parts: the first part computes gcd(a,b) in multiple steps and the second part fills in the corresponding x, y for each step in the first part in the reversed order.

At each step in the first part, if a > b in the previous step, we exchange a and b. Note that this can only happen at the first step. The color of the cells in the first two rows indicating this exchange process. Otherwise, we let a(i) = b(i-1) and b(i) = a(i-1)%b(i-1), where a(r) and b(r) are the value of a and b in row r. Therefore, the color of a cell (p, q) is always the same as the cell (p, q-1), where p and q are column and row numbers of a cell, respectively. This procedure repeats until a is divisible to b. In our case, since gcd(a,b) is always 1 due to the fact that e and φ(n) are co-prime, the first part always terminates at b = 1.

Then, we start filling x and y for each step in the first part in the reversed order. This means, assuming we have b = 1 in row k, we have a(k+i) = a(k-i) and b(k+i) = b(k-i). Note that it is always true to let x = 0 and y = 1 for the row k. At each step i, we let a(k+i) = a(k-i) and b(k+i) = b(k-i), and then compute the value of x and y as x(k+i) = y(k+i-1) and y(k+i) = x(k+i-1) - y(k+i-1)× {a(k+i)/b(k-i)}. Hence, the color of a cell (x, r) is always the same as the cell (y, r-1). Finally, if a and b exchange values in the first two rows, we exchange the value of x and y in the last two row.

Factorization Page

Fermat Sub-page

This sub-page shows how to factorize n using the Fermat Factorization. Assume that n=k2-h2, the calculation starts with k being the smallest integer larger than the square root of n. Then, in each iteration k is increased by one until the corresponding h is an integer.

Pollard Sub-page

This sub-page shows how to factorize n using the Pollard p-1 Factorization. The initial value of B is selected to be the minimum that could give a non-trivial factorization of n.

To change the value of B, enter a new value in the line edit and press return key.

To show the calculation of p using the Euclidean Algorithm, press "gcd(b-1, n)".

Attacks Page

Chosen Plaintext Attack Sub-page

This sub-page shows how to forge the sender's signature S without knowing the private key d. It starts from the calculation of signature S. The eavesdropper then modify the message M to obtain M' and ask the sender to sign the message M'. If the sender sign the message M', the eavesdropper can for calculate the original signature S from the new one S'.

Chosen Ciphertext Attack Sub-page

This sub-page shows how to recover the plaintext M without knowing the private key d. It starts from the calculation of ciphertext C. The eavesdropper then modify C to obtain M. And the receiver receives M and decrypts the ciphertext C. If the eavesdropper could get C, the plaintext M can be recovered from C.

Common Modulus Attack Sub-page

This sub-page shows how to recover the plaintext M without knowing the private key d, if M is encrypt by two different public keys but the same modulus. It starts from the encryption of M using two public keys e1 and e2 to obtain ciphertexts C1 and C2. The eavesdropper calculates x and y subject to e1x+e2=1. The plaintext M can be recovered from C1xC2y.