Use the RSA cipher to decrypt the word TfG.

Question

Q) Use the RSA cipher to decrypt the word TfG. The public key is N=221, e=5. Decrypt a single letter at a time. You may use an Excel spreadsheet but for full marks you must explain each step of your calculation.

Answer 1

N=pq=221=13×17.

(p-1)(q-1)=12×16=192.

e=5 (encryption exponent).

The decryption exponent is d, such that:

de=1 mod (p-1)(q-1):

5d=1 mod 192.

5d=192m+1,

When m=2, 5d=385, decryption factor d=77; 5×77=1 mod 192.

Plaintext=Cᵈmod N = C⁷⁷ mod 221.

For decrypted Tfg, T=64+20=84, f=96+6=102, g=103.

So C=84⁷⁷ mod 221.

b=84, e=77=115₈=1001101.

The next step is to use modulo exponentiation and to apply d to decrypt each letter.

TABLE FOR DECRYPTION OF “T” (ASCII CODE 84₁₀, 124₈, 1010100₂)

Binary e (reverse bits)	x, x₀=1	b (base), b₀=84
1	x₁=x₀b₀ mod 221 = 84	b₁=b₀² mod 221 = 205
0	x₁=84 (no change)
1	x₂=x₁b₁ mod 221 = 203	b₂=b₁² mod 221 = 35
1	x₃=x₂b₂ mod 221 = 33	b₃=b₂² mod 221 = 120
0	x₃=33
0	x₃=33
1	x₄=x₃b₃ mod 221 = 203₁₀, 313₈, 11001011₂

TABLE FOR DECRYPTION OF “f” (ASCII CODE 102₁₀, 146₈, 1100110₂)

Binary e	x, x₀=1	b (base), b₀=102
1	x₁=x₀b₀ mod 221 = 102	b₁=b₀² mod 221 = 17
0	x₁=102 (no change)
1	x₂=x₁b₁ mod 221 = 187	b₂=b₁² mod 221 = 68
1	x₃=x₂b₂ mod 221 = 119	b₃=b₂² mod 221 = 204
0	x₃=119
0	x₃=119
1	x₄=x₃b₃ mod 221 = 187₁₀, 273₈, 10111011₂

TABLE FOR DECRYPTION OF “g” (ASCII CODE 103₁₀, 147₈, 1100111₂)

Binary e	x, x₀=1	b (base) b₀=103
1	x₁=x₀b₀ mod 221 = 103	b₁=b₀² mod 221 = 1
0	x₁=103 (no change)
1	x₂=x₁b₁ mod 221 = 103	b₂=b₁² mod 221 = 1
1	x₃=x₂b₂ mod 221 = 103	b₃=b₂² mod 221 = 1
0	x₃=103
0	x₃=103
1	x₄=x₃b₃ mod 221 = 103₁₀, 147₈, 1100111₂