Scribd
Upload
2 views3 pages

Module 2 Problems-1

The document explains the Chinese Remainder Theorem (CRT) and provides solutions for two sets of congruences, resulting in X ≡ 156 (mod 315) and X ≡ 158 (mod 1155). It also details the RSA algorithm for key generation, encryption, and decryption, applying it to given values to find the public and private keys, as well as the encrypted and decrypted messages. Lastly, it describes the Diffie-Hellman key exchange algorithm, calculating public keys and the shared secret key K = 9.

Uploaded by

venkatsubhash382
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
2 views3 pages

Module 2 Problems-1

The document explains the Chinese Remainder Theorem (CRT) and provides solutions for two sets of congruences, resulting in X ≡ 156 (mod 315) and X ≡ 158 (mod 1155). It also details the RSA algorithm for key generation, encryption, and decryption, applying it to given values to find the public and private keys, as well as the encrypted and decrypted messages. Lastly, it describes the Diffie-Hellman key exchange algorithm, calculating public keys and the shared secret key K = 9.

Uploaded by

venkatsubhash382
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Q12) State the Chinese Remainder Theor em and find x for the given congruences using CRT.

(a) x ≡ 1 (mod 5), x ≡ 2 (mod 7), x ≡ 3 (mod 9)


(b) x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7), x ≡ 4 (mod 11)

Chinese Remainder Theorem (CRT)


If
X ≡ a1 (mod m1)
X ≡ a2 (mod m2)
…
where m1, m2, … are pairwise coprime, then there exists a unique solution modulo M = m1 × m2 ×
…
(a) Find X

Given:
X ≡ 1 (mod 5)
X ≡ 2 (mod 7)
X ≡ 3 (mod 9)

m1 = 5, m2 = 7, m3 = 9

M = m1 × m2 × m3 = 315

M1 = 63, M2 = 45, M3 = 35

Inverse values:
63 inverse mod 5 = 2
45 inverse mod 7 = 5
35 inverse mod 9 = 8

X = (1×63×2 + 2×45×5 + 3×35×8) mod 315


X = 1416 mod 315
X = 156

Answer:
X ≡ 156 (mod 315)

(b) Find X

Given:
X ≡ 2 (mod 3)
X ≡ 3 (mod 5)
X ≡ 2 (mod 7)
X ≡ 4 (mod 11)

m1 = 3, m2 = 5, m3 = 7, m4 = 11
M = m1 × m2 × m3 × m4 = 1155
M1 = 385, M2 = 231, M3 = 165, M4 = 105

Inverse values:
385 inverse mod 3 = 1
231 inverse mod 5 = 1
165 inverse mod 7 = 4
105 inverse mod 11 = 2

X = (2×385×1 + 3×231×1 + 2×165×4 + 4×105×2) mod 1155


X = 3623 mod 1155
X = 158

Answer:
X ≡ 158 (mod 1155)
Q 15) Explain the RSA algorithm for key generation, encryption, and decryption. Apply RSA algorithm for the
following data:

p = 7, q = 11, e = 17, Message M = 8

RSA Algor ithm

Key Gener ation:


1. Select two prime numbers p and q
2. Compute n = p × q
3. Compute φ(n) = (p − 1)(q − 1)
4. Choose e such that 1 < e < φ(n) and gcd(e, φ(n)) = 1
5. Find d such that (e × d) mod φ(n) = 1

Encr yption:

C = M^e mod n

Decr yption:

M = C^d mod n

Given:

p = 7, q = 11, e = 17, M = 8

n = p × q = 77

φ(n) = (7 − 1)(11 − 1) = 60

Find d:

17 × d mod 60 = 1

d = 53

Public Key: (e, n) = (17, 77)

Pr ivate Key: (d, n) = (53, 77)

Encr yption:

C = 8^17 mod 77 = 57

Decr yption:

M = 57^53 mod 77 = 8

Recover ed Message: 8
Q. 19) User Alice and Bob exchange the key using the Diffie–Hellman key exchange algor ithm.

Assume:

α = 5, q = 83, Xₐ = 6, Xᵦ = 10

Find Yₐ, Yᵦ, and the shar ed secr et key K.

Sol) Diffie-Hellman Key Exchange Algor ithm

Given:

α = 5, q = 83

XA = 6, XB = 10

Step 1: Compute Public Keys

YA = α^XA mod q

YA = 5^6 mod 83 = 21

YB = α^XB mod q

YB = 5^10 mod 83 = 11

Step 2: Compute Shar ed Secr et Key

K = YB^XA mod q

K = 11^6 mod 83 = 9

Shar ed Secr et Key:

K=9

You might also like