- 2072 Chaitra · 8 marks
RSA steps; encrypt word CAT
Short answer
RSA steps: choose primes p and q, compute n=pq and phi=(p-1)(q-1), choose e coprime to phi, compute d as inverse of e mod phi; public key (e,n), private key (d,n); encrypt C=M^e mod n, decrypt M=C^d mod n. With p=7, q=11, e=13, d=37, CAT (3,1,20) encrypts to 38, 1, 69 and decrypts back to CAT.
Write down the steps involved in the RSA encryption algorithm. Encrypt the word CAT using the RSA algorithm, choosing suitable data for encryption by yourself according to the RSA algorithm.
Steps of the RSA algorithm
- Choose two distinct prime numbers p and q.
- Compute n = p × q (the modulus; n is part of both keys).
- Compute Euler's totient φ(n) = (p − 1)(q − 1).
- Choose a public exponent e such that 1 < e < φ(n) and gcd(e, φ(n)) = 1.
- Compute the private exponent d with d × e ≡ 1 (mod φ(n)).
- Public key KU = (e, n); private key KR = (d, n).
- Encryption: C = Mᵉ mod n, where M < n.
- Decryption: M = Cᵈ mod n.
Encrypting CAT
Convert letters to numbers: A = 1, B = 2, ... so C = 3, A = 1, T = 20.
| Step | Calculation | Value |
|---|---|---|
| p, q | choose p = 7, q = 11 | |
| n | 7 × 11 | 77 |
| φ(n) | 6 × 10 | 60 |
| e | choose e = 13, gcd(13, 60) = 1 | 13 |
| d | 13 × d ≡ 1 mod 60; 13 × 37 = 481 = 8 × 60 + 1 | 37 |
Public key = (13, 77); private key = (37, 77). All values are less than 77.
| Letter | M | Encryption C = M¹³ mod 77 | Decryption M = C³⁷ mod 77 |
|---|---|---|---|
| C | 3 | 3¹³ mod 77 = 38 | 38³⁷ mod 77 = 3 |
| A | 1 | 1¹³ mod 77 = 1 | 1³⁷ mod 77 = 1 |
| T | 20 | 20¹³ mod 77 = 69 | 69³⁷ mod 77 = 20 |
Working
- C: encrypt: 3^1 = 3, 3^2 = 9, 3^4 = 4, 3^8 = 16 (all mod 77); 13 = 1 + 4 + 8, so 3^13 = 3 × 4 × 16 mod 77 = 38. Decrypt: 38^1 = 38, 38^2 = 58, 38^4 = 53, 38^8 = 37, 38^16 = 60, 38^32 = 58 (all mod 77); 37 = 1 + 4 + 32, so 38^37 = 38 × 53 × 58 mod 77 = 3.
- A: encrypt: 1^1 = 1, 1^2 = 1, 1^4 = 1, 1^8 = 1 (all mod 77); 13 = 1 + 4 + 8, so 1^13 = 1 × 1 × 1 mod 77 = 1. Decrypt: 1^1 = 1, 1^2 = 1, 1^4 = 1, 1^8 = 1, 1^16 = 1, 1^32 = 1 (all mod 77); 37 = 1 + 4 + 32, so 1^37 = 1 × 1 × 1 mod 77 = 1.
- T: encrypt: 20^1 = 20, 20^2 = 15, 20^4 = 71, 20^8 = 36 (all mod 77); 13 = 1 + 4 + 8, so 20^13 = 20 × 71 × 36 mod 77 = 69. Decrypt: 69^1 = 69, 69^2 = 64, 69^4 = 15, 69^8 = 71, 69^16 = 36, 69^32 = 64 (all mod 77); 37 = 1 + 4 + 32, so 69^37 = 69 × 15 × 64 mod 77 = 20.
Ciphertext = 38, 1, 69. Decrypting gives 3, 1, 20 = CAT.
Note: the letter A = 1 always gives 1ᵉ = 1, a weakness of encoding single letters; real RSA pads the message.
Answer: public key (13, 77), private key (37, 77); CAT encrypts to 38, 1, 69 and decrypts back to CAT.
✓ Answer checked by Claude Opus 5.5 (high effort)
Related questions
- RSA encrypt/decrypt OVEL · Computer Networks and Security, chapter 8
- RSA algorithm with example · Computer Networks and Security, chapter 8 · asked 4×
- Data Encryption Standard operation · Computer Networks and Security, chapter 8
- IC manufacturing steps; top-down F = xz + y · Embedded System, chapter 8
- Short note: Routing algorithm in data communication · Telecommunications, chapter 8 · asked 2×
- Total station features and data recording steps · Surveying II, chapter 9
- ADC804 with 8255 control word and program · Instrumentation II, chapter 4