HW4

4.1 Encrypt and decrypt by means of the RSA algorithm with the following system parameters

1

$n = p \cdot q = 3 \cdot 11 = 33$
$\phi(n) = (p - 1)(q - 1) = 2 \cdot 10 = 20$
$7 \cdot e \equiv 1 \pmod{20}$
$7 \cdot 3 = 21 \equiv 1 \pmod{20}$, $e = 3$

Public$(e, n) = (3, 33)$,
Private $(d, n) = (7, 33)$

$y \equiv 5^3 \pmod{33}$
$y = 125 \pmod{33}$

$26 \equiv -7 \pmod{33}$
$x \equiv 26^7 \pmod{33}$
$(-7)^7 \equiv 4 \cdot (-7) = -28 \equiv 5 \pmod{33}$
$x = 5$

2

$n = 5 \cdot 11 = 55$
$\phi(n) = 40$
$3 \cdot d \equiv 1 \pmod{40}$
Public $(e, n) = (3, 55)$
Private $(d, n) = (27, 55)$
$y \equiv 9^3 \pmod{55}$
$x \equiv 14^{27} \pmod{55}$
$14^2 = 196 \equiv 31 \pmod{55}$
$14^4 \equiv 31^2 = 961 \equiv 26 \pmod{55}$
$14^8 \equiv 26^2 = 676 \equiv 16 \pmod{55}$
$14^{16} \equiv 16^2 = 256 \equiv 36 \pmod{55}$

$14^{27} \equiv 36 \cdot 16 \cdot 31 \cdot 14 \pmod{55}$
$36 \cdot 14 = 504 \equiv 9 \pmod{55}$
$x = 9$

2. Compute the two public keys and the common key for the DHKE scheme with the parameters p = 467, α = 2, and

1

Alice's Public Key: $A \equiv \alpha^a \pmod p$
Bob's Public Key: $B \equiv \alpha^b \pmod p$
Common Secret Key: $K \equiv B^a \pmod p \equiv A^b \pmod p$

$p = 467, \alpha = 2, a = 3, b = 5$

$A \equiv 2^3 \pmod{467}$, $A = 8$
$B \equiv 2^5 \pmod{467}$, $B = 32$

$K \equiv 32^3 \pmod{467}$
$K = 32768 \pmod{467}$
$32768 = 467 \cdot 70 + 78$
$K = 78$

Alice's Public Key: $A = 8$
Bob's Public Key: $B = 32$
Common Key: $K = 78$

2

$p = 467, \alpha = 2, a = 400, b = 134$
$A \equiv 2^{400} \pmod{467}$
$A = 137$
$B \equiv 2^{134} \pmod{467}$
$B = 84$

$K \equiv 84^{400} \pmod{467}$

Alice's Public Key: $A = 137$
Bob's Public Key: $B = 84$
Common Key: $K = 90$

3 Encrypt the following messages with the Elgamal scheme (p = 467 and α = 2)

ElGamal Formula

$\beta \equiv \alpha^d \pmod p$
$C_1 \equiv \alpha^i \pmod p$
$K_M \equiv \beta^i \pmod p$
$C_2 \equiv x \cdot K_M \pmod p$

$K_M \equiv C_1^d \pmod p$
$x \equiv C_2 \cdot K_M^{-1} \pmod p$

1. $k_{pr} = d = 105, i = 213, x = 33$
   $\beta \equiv 2^{105} \pmod{467} = 226$
   $C_1 \equiv 2^{213} \pmod{467} = 29$
   $K_M \equiv 226^{213} \pmod{467} = 234$
   $C_2 \equiv 33 \cdot 234 \equiv 7722 \pmod{467} = 250$
   $(C_1, C_2) = (29, 250)$

   $K_M \equiv 29^{105} \pmod{467} = 234$
   $234^{-1} \pmod{467} = 2$
   $x \equiv 250 \cdot 2 = 500 \equiv 33 \pmod{467}$

2. $k_{pr} = d = 105, i = 123, x = 33$
   $\beta \equiv 2^{105} \pmod{467} = 226$
   $C_1 \equiv 2^{123} \pmod{467} = 274$
   $K_M \equiv 226^{123} \pmod{467} = 353$
   $C_2 \equiv 33 \cdot 353 \equiv 11649 \pmod{467} = 441$
   $(C_1, C_2) = (274, 441)$
   Decrypt
   $K_M \equiv 274^{105} \pmod{467} = 353$
   $353^{-1} \pmod{467} = 340$
   $x \equiv 441 \cdot 340 = 149940 \pmod{467} = 33$
   

3. $k_{pr} = d = 300, i = 45, x = 248$
   $\beta \equiv 2^{300} \pmod{467} = 153$
   $C_1 \equiv 2^{45} \pmod{467} = 220$
   $K_M \equiv 153^{45} \pmod{467} = 328$
   $C_2 \equiv 248 \cdot 328 \equiv 81344 \pmod{467} = 86$
   $(C_1, C_2) = (220, 86)$
   Decrypt
   $K_M \equiv 220^{300} \pmod{467} = 328$
   $328^{-1} \pmod{467} = 383$
   $x \equiv 86 \cdot 383 = 32938 \pmod{467} = 248$

4. $k_{pr} = d = 300, i = 47, x = 248$
   $\beta \equiv 2^{300} \pmod{467} = 153$
   $C_1 \equiv 2^{47} \pmod{467} = 413$
   $K_M \equiv 153^{47} \pmod{467} = 314$
   $C_2 \equiv 248 \cdot 314 \equiv 77872 \pmod{467} = 350$
   $(C_1, C_2) = (413, 350)$
   Decrypte
   $K_M \equiv 413^{300} \pmod{467} = 314$
   $314^{-1} \pmod{467} = 409$
   $x \equiv 350 \cdot 409 = 143150 \pmod{467} = 248$

4.4 Considering the four examples from Problem we see that the Elgamal scheme is

nondeterministic: A given plaintext x has many valid ciphertext, e.g., both x = 33 and x =
248 have the same ciphertext in the problem above.

1. Why is the Elgamal signature scheme nondeterministic?

The ElGamal scheme is nondeterministic because a random ephemeral key ($i$) is chosen for every encryption process. Even if the plaintext and the public key remain identical, a different value of $i$ will produce a completely different ciphertext pair. This inherent randomness prevents attackers from analyzing repeating patterns.

2. How many valid ciphertexts exist for each message x (general expression)?

How many are there for the system in Problem 4.1 (numerical answer)?
The number of valid ciphertexts corresponds to the number of available choices for the random variable $i$. Since $i$ is selected from the multiplicative group modulo $p$, the general expression is $p - 1$.
For the system in Problem 4.1 where $p = 467$, the numerical answer is $466$.

3. Is RSA crypto system nondeterministic once the public key has been chosen?

No, textbook RSA is deterministic. The algorithm relies on the fixed mathematical equation $y \equiv x^e \pmod n$. Unless an external randomized padding scheme (such as OAEP) is applied, encrypting the same plaintext with a given public key will always generate the exact same ciphertext.

5. Given EC:

E: 𝑦2 ≡ 𝑥3 + 2𝑥 + 2 mod 17.
All points on the curve form a cyclic group and that the order is #E = 19. The basepoint/primitive element is 𝑃 = (5,1), please calculate 2P, 3P, 4P, 5P, 6P, 7P, 8P, 9P, 10P, 11P, 12P, 13P, 14P, 15P, 16P, 17P, 18P and 19P

Elliptic Curve $E: y^2 \equiv x^3 + 2x + 2 \pmod{17}$
Base point $P = (5, 1)$
Order $\#E = 19$

$P = (5, 1)$
$2P = (6, 3)$
$3P = 2P + P = (10, 6)$
$4P = 3P + P = (3, 1)$
$5P = 4P + P = (9, 16)$
$6P = 5P + P = (16, 13)$
$7P = 6P + P = (0, 6)$
$8P = 7P + P = (13, 7)$
$9P = 8P + P = (7, 6)$

Using Symmetry
$(19-k)P = -kP$, $(x, -y \pmod p)$

$10P = -9P = (7, -6 \pmod{17}) = (7, 11)$
$11P = -8P = (13, -7 \pmod{17}) = (13, 10)$
$12P = -7P = (0, -6 \pmod{17}) = (0, 11)$
$13P = -6P = (16, -13 \pmod{17}) = (16, 4)$
$14P = -5P = (9, -16 \pmod{17}) = (9, 1)$
$15P = -4P = (3, -1 \pmod{17}) = (3, 16)$
$16P = -3P = (10, -6 \pmod{17}) = (10, 11)$
$17P = -2P = (6, -3 \pmod{17}) = (6, 14)$
$18P = -P = (5, -1 \pmod{17}) = (5, 16)$
$19P = \mathcal{O}$ (Point at infinity)