Scribd
Upload
35 views6 pages

Cryptography and Modular Arithmetic Solutions

The document outlines various mathematical problems and solutions related to number theory and cryptography. It includes the Extended Euclidean Algorithm, modular arithmetic, RSA algorithm, Diffie-Hellman key exchange, and encryption techniques. Each problem is solved step-by-step, demonstrating the application of theoretical concepts in practical scenarios.

Uploaded by

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

Cryptography and Modular Arithmetic Solutions

The document outlines various mathematical problems and solutions related to number theory and cryptography. It includes the Extended Euclidean Algorithm, modular arithmetic, RSA algorithm, Diffie-Hellman key exchange, and encryption techniques. Each problem is solved step-by-step, demonstrating the application of theoretical concepts in practical scenarios.

Uploaded by

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

1.

Use the Extended Euclidean Algorithm to find integers x , y such


that 65 x +40 y=gcd ⁡( 65 , 40).
2. Solve for x : 17 x ≡ 3 ( mod 26
3. Determine whether the set {0 ,1 , 2 ,3 }with addition and multiplication
modulo 4 forms a field.
4. For the key “KEY”, perform the first 5 steps of the RC4 key-
scheduling algorithm.
5. Combine modular arithmetic and cryptography: Encrypt the
message "HELLO" using a multiplicative cipher modulo 26 with
key k =7.
6. If p=7 , q=11, and e=17 , compute ϕ (n) and find d such that
ed ≡1(mod ϕ (n)).
7. Compute 7222 mod 40 using Euler’s theorem.
8. For p=11 and q=19 and choose d=17. Apply RSA algorithm where
cipher message = 80 and thus find the plain text.
9. Determine the plaintext 'M' from the cipher text (C=106, N=143,
e=11) using RSA algorithm.
10. Alice and Bob use the Diffie - Hellman key exchange technique
with a common prime number 11 and a primitive root of 2. If Alice
and Bob choose distinct secret integers as 9 and 3, respectively,
then compute the shared secret key.
11. Encrypt and decrypt HELP using the key matrix

K= [ ]
3 3
2 5
12. Encrypt the word "Network Security" with keyword "crypto"
using play cipher.

1️⃣ Use the Extended Euclidean Algorithm to find integers x , y such


that 65 x +40 y=gcd ⁡( 65 , 40).

Step 1: Apply Euclid’s Algorithm

65=1× 40+2540=1 ×25+1525=1× 15+1015=1× 10+510=2× 5+0

✅ So, gcd ⁡(65 , 40)=5 .

Step 2: Back-substitute to find x , y

From 15=1× 10+5→ 5=15−1(10)


Substitute 10=25−1(15):

5=15−(25−15)=2 (15)−25

Substitute 15=40−25:

5=2(40−25)−25=2(40)−3(25)

Substitute 25=65−40:

5=2(40)−3 (65−40)=2(40)−3(65)+3(40)=5(40)−3( 65)

✅ Final Result:

5=(−3)(65)+(5)(40)

So x=−3 , y =5.

2️⃣ Solve for x : 17 x ≡ 3 (mod 26)

We must find x such that:

17 x ≡ 3(mod 26)

Step 1: Find the modular inverse of 17 mod 26

We need 17 x ≡ 1(mod 26).

Use Extended Euclidean Algorithm:

26=1(17)+917=1(9)+89=1(8)+18=8(1)+0

So, gcd ⁡(17 , 26)=1.

Now back-substitute:

1=9−1(8)8=17−1( 9) → 1=9−1(17−9)=2(9)−17
9=26−17→ 1=2 (26−17)−17=2(26)−3(17)

Thus,

−3(17)≡1( mod 26)

or 23(17)≡1(mod 26).

✅ So, the modular inverse of 17 mod 26 is 23.

Step 2: Solve for x

x ≡ 3 ×23( mod 26)x ≡ 69(mod 26 )⇒ x ≡17(mod 26)

✅ Final Answer:
x=17
3️⃣ Determine whether the set {0 ,1 , 2 ,3 }with addition and
multiplication modulo 4 forms a field.

Step 1: Check Field Requirements

A field requires:

1. Closure, associativity, commutativity for addition/multiplication ✔

2. Additive identity (0) and multiplicative identity (1) ✔

3. Every nonzero element must have a multiplicative inverse ❌

Step 2: Test Inverses modulo 4

Compute products mod 4:

 1 ×1=1→ inverse of 1 is 1

 2 ×1=2 , 2 ×2=0 , 2× 3=2→ no inverse for 2

 3 ×3=1→ inverse of 3 is 3

Element 2 has no inverse modulo 4.

✅ Conclusion:
{0 ,1 , 2 ,3 } under mod 4 is not a field (it’s a ring only).

4️⃣ For the key “KEY”, perform the first 5 steps of the RC4 key-
scheduling algorithm (KSA).

Given:
Key = “KEY” = ASCII → [75, 69, 89]
Key length ¿ 3.

Initialize

S=[0 , 1, 2 , ..., 255]K [i]=Key[imod 3]=[75 ,69 , 89 , 75 ,69 ,89 , ...]

Step-by-Step (First 5 Steps)

We perform:

j=( j+ S [i]+ K [i])mod 256 , then swap S [i]↔ S [ j]

Start with j=0.


S[i K[i Swap(S[i], Resulting
i j (new)
] ] S[j]) swap

Swap S[0], S[0]=75,


00 75 (0+0+75)=75
S[75] S[75]=0

(75+1+69)=1 Swap S[1], S[1]=145,


11 69
45 S[145] S[145]=1

(145+2+89)= Swap S[2], S[2]=236,


22 89
236 S[236] S[236]=2

(236+3+75)= Swap S[3], S[3]=58,


33 75
58 S[58] S[58]=3

(58+4+69)=1 Swap S[4], S[4]=131,


44 69
31 S[131] S[131]=4

✅ After 5 steps:
Partial state changes:


S[0]=75 , S [1 ]=145 , S [2]=236 , S[3]=58 , S [4 ]=131 , S [75 ]=0 , S[145]=1 , S [236 ]=2 , S [58 ]=3 , S[131

5️⃣ Encrypt "HELLO" using a multiplicative cipher mod 26 with key


k =7.

Step 1: Represent letters as numbers

A=0, B=1, …, Z=25


H=7, E=4, L=11, L=11, O=14

Step 2: Encryption rule

C=(kP) mod 26

Step 3: Compute

Lett C = 7P mod Cipher


P
er 26 letter

49 mod 26 =
H 7 X
23

28 mod 26 =
E 4 C
2

L 1 77 mod 26 = Z
Lett C = 7P mod Cipher
P
er 26 letter

1 25

1 77 mod 26 =
L Z
1 25

1 98 mod 26 =
O U
4 20

✅ Ciphertext:
XCZZU

6️⃣ If p=7 , q=11 ,e=17 , compute ϕ (n)and find d such that ed ≡1(mod ϕ (n)).

Step 1: Compute n and φ(n)

n=pq=7 × 11=77ϕ (n)=( p−1)(q−1)=6 × 10=60

Step 2: Find d such that

17 d ≡1(mod 60)

Use Extended Euclidean Algorithm:

60=3(17)+917=1(9)+89=1(8)+18=8(1)+0

Back-substitute:
1=9−1(8)=9−1(17−9)=2(9)−179=60−3 (17)

1=2 (60−3 (17))−17=2(60)−7(17)

✅ So, −7(17)≡1 (mod 60)

d ≡−7 ≡53(mod 60)

✅ Final Answer:

ϕ (n)=60 , d=53

7️⃣ Compute 7222 mod 40 using Euler’s Theorem.

Step 1: Verify gcd

gcd ⁡(7 , 40)=1, so Euler’s theorem applies.

Step 2: Compute ϕ (40)


3 1 1 1 4
40=2 ×5 ⇒ ϕ (40)=40 (1− )(1− )=40 × × =16
2 5 2 5
Step 3: Apply Euler’s theorem
16
7 ≡1( mod 40)

Now reduce exponent:

222=16 × 13+147222 =¿

Step 4: Compute 714 mod 40

Compute successive powers mod 40:


2 4 2
7 =49 ≡9 , 7 =9 =81 ≡1

So 7 4 ≡ 1(mod 40) .

Then:
14
7 =¿
✅ Final Answer:
222
7 ≡ 9( mod 40)

Common questions

Powered by AI

To initialize KSA with the key "KEY" (ASCII values [75, 69, 89]), initialize array S to [0, 1, 2, ..., 255]. Then, compute j as (j + S[i] + K[i]) mod 256 and swap S[i] with S[j] for each i from 0. After five steps: i = 0, 1, 2, 3, 4 result in swaps that partially transform S: S[0]=75, S[1]=145, S[2]=236, S[3]=58, S[4]=131, changing respective j values .

Euler's theorem states if gcd(a, n) = 1, then a^φ(n) ≡ 1 (mod n). With 7^222 mod 40, verify gcd(7, 40) = 1. Calculate φ(40) where 40 = 2^3×5: φ(40) = 16. By Euler, 7^16 ≡ 1 (mod 40). Express 222 as 16×13 + 14, then 7^222 = (7^16)^13 × 7^14. Since (7^16 ≡ 1), 7^14 mod 40 = (7^2)^7 = 9^7 which simplifies via successive squaring to 9 (mod 40), yielding result 7^222 ≡ 9 (mod 40).

First, find the modular inverse of 17 mod 26 using the Extended Euclidean Algorithm since 17x ≡ 1 (mod 26). Identify: 26 = 1(17) + 9, yielding gcd(17, 26) = 1, thus 17 is invertible. Back-substitution gives 1 = 2(26) - 3(17), so 23 is the modular inverse. Then, solve x ≡ 3×23 (mod 26), calculating x ≡ 69(mod 26), resulting in x ≡ 17(mod 26).

Given p = 7, q = 11, calculate n = pq = 77 and φ(n) = (p-1)(q-1) = 60. To find decryption key d, solve 17d ≡ 1 (mod 60) using the Extended Euclidean Algorithm: 60 = 3(17) + 9; 9 = 17 - 1*8; 1 = 2(9) - 17 = 2(60-3*17) - 17 = 2*60 - 7*17. Therefore, -7*17 ≡ 1 (mod 60) and d ≡ -7 ≡ 53 (mod 60), yielding d = 53 .

With a prime number 11 and primitive root 2, Alice selects a secret integer 9, computes A = 2^9 mod 11 = 6. Bob chooses 3, computes B = 2^3 mod 11 = 8. They then exchange A and B, and compute the shared key: Alice computes K = B^9 mod 11 = 8^9 mod 11 = 2, while Bob computes K = A^3 mod 11 = 6^3 mod 11 = 2. Shared secret key is K = 2 .

The set {0,1,2,3} does not form a field under addition and multiplication modulo 4 because not every nonzero element has a multiplicative inverse. Specifically, while 1 has an inverse of 1 and 3 has an inverse of 3 in this system, 2 does not have an inverse as demonstrated by multiplication checks (e.g., 2×1 = 2, 2×2 = 0). Therefore, it fails field properties and remains a ring .

In a multiplicative cipher mod 26 with key k=7, first represent each letter by its position in the alphabet: 'H' = 7, 'E' = 4, 'L' = 11, 'L' = 11, 'O' = 14. The encryption C=(kP) mod 26 results in transformed values: H→ 49 ≡ 23(X), E→ 28 ≡ 2(C), L→ 77 ≡ 25(Z), L→ 77 ≡ 25(Z), O→ 98 ≡ 20(U), producing the ciphertext XCZZU .

To find integers x and y such that 65x + 40y = gcd(65, 40), you apply the Extended Euclidean Algorithm. First, determine gcd(65, 40) by repeated division: 65 = 1*40 + 25, 40 = 1*25 + 15, 25 = 1*15 + 10, 15 = 1*10 + 5, 10 = 2*5 + 0. Thus, gcd(65, 40) = 5. Backtrack to express 5 as a linear combination: start with 5 = 15 - 1*10, substitute back using previous equation values until reaching 65 and 40 relations ultimately resulting in 5 = (-3)*65 + 5*40. So x = -3, y = 5 .

In a Playfair cipher, encrypt 'Network Security' using 'crypto' as keyword forms a grid, omitting duplicate letters and J. 'Crypto' builds as C, R, Y, P, T, O : adding remaining alphabet completes matrix. Every letter pair in the message forms rectangles, shifting rows or columns accordingly. Starting pairs (e.g., 'NE', 'TU', 'TR') transform using grid positions. Each such adjusted results encrypts the message. Exact resultant ciphertext depends on reconstructed keyword path .

To encrypt 'HELP' using the key matrix K = [[3, 3], [2, 5]], first convert letters to numbers: H=7, E=4, L=11, P=15. Form column vectors, e.g., [7, 4], [11, 15]. Multiply each vector by K mod 26. For instance, K[7, 4] = [(3*7 + 3*4) % 26, (2*7 + 5*4) % 26] = [33 mod 26, 34 mod 26] = [7, 8] (G, I). Continuing, encrypts 'HELP' to final ciphertext [G, I, ... rest cells follow similar steps].

You might also like