CIS-2011-N, ICA1: Cryptography Basics and Solutions

This document presents a detailed solution to a cryptography basics assignment, addressing key concepts in information security. The solution covers the RSA encryption algorithm, including finding private keys and decrypting messages. It also explains the Feige-Fiat-Shamir scheme, outlining the steps for Peggy and Victor to establish trust using prime numbers and random selections. Furthermore, the assignment explores the Diffie-Hellman protocol, demonstrating how to securely exchange keys between multiple parties. The document provides step-by-step solutions, calculations, and explanations for each cryptographic method, making it a valuable resource for students studying information security and cryptography.

Running head: CRYPTOGRAPHY BASICS
CRYPTOGRAPHY BASICS
Name of the Student
Name of the University
Author Note

1CRYPTOGRAPHY BASICS
Table of Contents
RSA..................................................................................................................................................2
Feige-Fiat-Shamir scheme...............................................................................................................4
Diffie-Hellman protocol..................................................................................................................5

2CRYPTOGRAPHY BASICS
RSA
1. Solution
Given public key (143, 11)
Here n = 143, e = 11
We know n = p x q
Hence the factor of the 143 = 11, 13
Now ∅ ( n ) =( p−1)×(q−1) [11, 13 one of them is p or q]
=> ∅ ( n )=10 ×12=120
Now for private key
=> d ×e=1 mod ∅ ( n )
=> d ×11=1 mod 120
Using Chinese remainder theorem
Multiply both side by 11
=> d (11 ×11)=1 1mod 120
=> d=11mod 120
Hence the d = 11, and private key pair is (143,11) Ans.
2. Solution
Key is given (143, 11)

3CRYPTOGRAPHY BASICS
Here n = 143
d = 11
Encrypted message = 111 4 88 57 116 67
Using formula m=cd mod n find decrypted message for each block of message where c =
encrypted message, d= private key and m = decrypted message.
For 111,
=> m=cd mod n
=> m=11111 mod 143=92
For 4,
=> m=cd mod n
=> m=411 mod 143=114
For 88,
=> m=cd mod n
=> m=8811 mod 143=3 4
For 57,
=> m=cd mod n
=> m=5711 mod 143=142
For 116,

4CRYPTOGRAPHY BASICS
=> m=cd mod n
=> m=11611 mod 143=37
For 67,
=> m=cd mod n
=> m=6 711 mod 143=81
Hence the decrypted message is (92 114 34 142 37 81)
This value in ASCII.
After converting it into text the message becomes = \r"Ž %Q Ans.
Feige-Fiat-Shamir scheme
3. Solution
The Feige-Fiat-Shamir scheme: Two trusted parties Peggy and Victor Selects two secret prime
number p and q. Next the n=pxq is public key for all users. Peggy selects a random number r,
such that r<n. Then she computes x=r2 modn and sends it to victor. Victor then replies Peggy as
a bit either 0 or 1. If the sent bit is 0 then she sends victor r. if b is 1 then she sends y=r × s mod n
. Now if b was 0 then victor verify x=r2 modn knowing Peggy knows √ x. If b was 1 then victor
verifies x= y2 × v mod n proving that Peggy
√ x
v knows
4. Solution
n= 15 and r=11
Public key v, is generated such that x2=v mod n

5CRYPTOGRAPHY BASICS
Now Peggy selects a number r that is 11 such that r<n.
Peggy computes x=r2 modn
=> x=112 mod 15 => x=121 mod 15 => x=1 mod 15
For x2 also the equation will be x2=1 mod 15
Hence v= 1.
Now the contents of the messages will be s= √ 1
v mod n
=> s= √ 1
1 mod 15 => s=1mod 15 Ans.
Diffie-Hellman protocol
Deffie-hellman protocol is not limited to sharing key between only two parties. It can be shared
between three peoples and even groups. To exchange key between Alice, bob and carol,
continuous iteration needs to be performed using agreement protocol. For example Alice, Bob
and Carol takes part with operation modulo P and agrees and algorithm parameters ‘p’ and ‘g’.
Suppose their private keys are a, b and c respectively.
First Alice computes with her key = ga and sends to bob.
Then bob computes it with his key ¿( g ¿¿ a)b ¿ and sends to carol.
Now carol computes it with her key = (g¿¿ a b)c ¿ = gabc and uses it.
Similarly,
First bob computes with his key = gb and sends to carol.

6CRYPTOGRAPHY BASICS
Then carol computes it with her key ¿( g ¿¿ b)c ¿ and sends to Alice.
Now Alice computes it with her key = (g¿¿ b c)a ¿ = gabc and uses it.
Finally
First carol computes with her key = gc and sends to Alice.
Then Alice computes it with her key ¿( g ¿¿ c)a ¿ and sends to bob.
Now bob computes it with his key = (g¿¿ ca)b ¿ = gabc and uses it.
Now they have successfully exchanged their keys. To crack the encryption the combination of
the keys will be required i.e. gabc .