RSA Encryption

Introduction to RSA

RSA (Rivest-Shamir-Adleman) is a public-key cryptography algorithm. In practice:

• It uses two keys: a public key and a private key.
• Public key (e, n): used to encrypt messages.
• Private key (d, n): used to decrypt messages.
• The security relies on the difficulty of factoring large prime numbers.

Key Generation Steps

1. Choose two large prime numbers: p and q.
2. Compute n:
   n = p * q
3. Compute Euler's totient function:
   φ(n) = (p-1)*(q-1)
4. Choose a public exponent e:
   It must be coprime with φ(n), typically e = 65537.
5. Compute the private exponent d:
   It must satisfy d * e ≡ 1 (mod φ(n)).

Resulting keys:

• Public: (e, n)
• Private: (d, n)

Encryption

To send a message m using the public key (e, n):

c = m^e mod n

Decryption

The recipient uses the private key (d, n) to decrypt c:

m = c^d mod n

Decryption using language's alphabet distribution

When decrypting a simple substitution cipher or numeric-encoded text without knowing the key, we can use a statistical approach based on English language patterns. One of the most powerful techniques is to apply quadgram analysis together with hill-climbing or simulated annealing to automatically search for the most likely plaintext.

1. Basic Idea

English text has not only frequent single letters (E, T, A, O, I, N…) but also common sequences of four letters, called quadgrams. Examples include:

• TION, NTHE, THER, THAT, OFTH, …

Each of these quadgrams occurs with a certain probability in normal English. By comparing how often they appear in a guessed plaintext to how often they appear in real text, we can measure how “English-like” the decryption is. The higher this score, the closer we are to the correct plaintext.

2. Practical Steps

1. Load or generate a table of known English quadgrams and their probabilities.
2. Start from an initial mapping between ciphertext symbols and letters — for example, based on letter frequency.
3. Decrypt the ciphertext using this mapping and compute the total quadgram score using log-probabilities:
   score = Σ log₁₀(P(quadgram))
4. Randomly swap two letters in the mapping and calculate the new score.
5. If the new score is higher, keep the change. Otherwise, sometimes still accept it with a small probability (this is the essence of simulated annealing).
6. Repeat many times, keeping the mapping that yields the highest score.

3. Example Pseudocode

load quadgram_table
best_key = random_mapping()
best_score = score(decrypt(ciphertext, best_key))

for iteration in range(N):
    new_key = swap_two_letters(best_key)
    new_score = score(decrypt(ciphertext, new_key))
    delta = new_score - best_score

    if delta > 0 or exp(delta / temperature) > random():
        best_key = new_key
        best_score = new_score

return decrypt(ciphertext, best_key)

4. Limitations

• Quadgram scoring assumes English plaintext. For other languages, a corresponding quadgram table must be used.
• The method is probabilistic — different runs may yield slightly different results, but longer ciphertexts improve reliability.
• A complete quadgram table is essential for good accuracy. You can download one from Practical Cryptography – Quadgram Data.

Quadgram Solver — Annealed Hill-Climb + Double Swap

Paste your ciphertext (space-separated tokens or continuous encrypted text), optionally load a full quadgram table, then press Run. Default settings work well; increase iterations/restarts for longer texts.

Ready.