CRYPTOGRAPHIC ALGORITHMS AND PROTOCOLS
1 1. KEY MANAGEMENT AND DISTRIBUTION CHALLENGES
Problem 1. Consider a key distribution center (KDC) that generates session keys for commu-
nication between users. For a particular communication session, Alice and Bob request a session
key from the KDC. The KDC generates two session keys KAB and KBA for communication be-
tween Alice and Bob. The KDC also generates a symmetric key KKDC to be used between the
KDC and Alice/Bob.
If the KDC sends KAB encrypted with KKDC to Alice and KBA encrypted with KKDC to Bob,
and Alice and Bob use these keys to communicate securely, what cryptographic algorithms are
being used here?
Solution 1. In this scenario, the KDC employs asymmetric cryptography to securely share ses-
sion keys with Alice and Bob. The KDC uses its symmetric key KKDC to encrypt the session keys
KAB and KBA before sending them to Alice and Bob. Once Alice and Bob receive the encrypted
session keys, they use KKDC to decrypt and obtain their respective session keys.
Therefore, the KDC uses symmetric cryptography (e.g., AES) to encrypt the session keys and
asymmetric cryptography (e.g., RSA) to securely share the symmetric key KKDC with Alice and
Bob.
2 Cryptographic Algorithms and Protocols
Problem:
Consider a block cipher algorithm using a 128-bit block size with a 256-bit key. Suppose an
attacker is able to perform a brute-force attack by trying all possible keys.
a) Calculate the total number of possible keys.
b) If the attacker can try 1 billion keys per second, estimate the time it would take to try all
possible keys.
c) If the attacker is able to reduce the key space to only 50
Solution:
a) The total number of possible keys can be calculated using the formula 2nwhere nis the key
size in bits. In this case, the key size is 256 bits.
Total number of possible keys = 2256 = 115792089237316195423570985008687907853269984665640564039457584007913129639936
b) To estimate the time it would take to try all possible keys, we divide the total number of keys
by the keys tried per second:
Time to try all keys =2256
1billion keys/second =115792089237316195423570985008687907853269984665640564039457584007913129639936
1billion
≈3.674 ×1057 seconds
To convert this to years, we divide by the number of seconds in a year (approximately 3.1536 ×
107seconds):
Time to try all keys in years ≈3.674×1057
3.1536×107≈1.165 ×1050 years
c) If the attacker is able to reduce the key space to only 50
Keys needed to try on average =2256
2= 2255 = 57896044618658097711785492504343953926634992332820282019728792003956564819969
3 3. VULNERABILITIES IN ASYMMETRIC ENCRYPTION SCHEMES
Problem 3. Consider the RSA encryption scheme with public key (e, N) = (7,187). An attacker
intercepts a message m= 65 encrypted using this public key.
a) Compute the private key d.
b) Determine the decrypted message.
Solution 3.
a) To compute the private key d, we need to find the value such that ed ≡1 (mod φ(N)), where
φ(N)is Euler’s totient function.
Given that N= 187, we first need to calculate φ(N):
φ(N)=(p−1)(q−1) = 10 ×18 = 180.
Next, we solve for d:
7d≡1 (mod 180).
Solving this congruence, we get d= 103.
b) To decrypt the message, we calculate cd(mod N), where cis the intercepted ciphertext.
m= 65103 (mod 187).
Using fast modular exponentiation, we can simplify this calculation:
652≡52 (mod 187),
654≡522≡64 (mod 187),
658≡642≡141 (mod 187),
6516 ≡1412≡145 (mod 187),
6532 ≡1452≡79 (mod 187),
6564 ≡792≡77 (mod 187).
Therefore,
65103 ≡65 ×6532 ×6516 ×652×651
≡65 ×79 ×145 ×52
≡64 (mod 187).
Hence, the decrypted message is m= 64.
4 4. CRYPTANALYSIS OF SYMMETRIC KEY ALGORITHMS
Problem 4. Consider a block cipher with a block size of 64 bits and a key size of 128 bits. An
attacker performs a known-plaintext attack where they obtain 10 plaintext-ciphertext pairs. Each
pair has a plaintext of 64 bits and a corresponding ciphertext of 64 bits. The attacker wants to
determine the key using this information.
a) What is the maximum number of key candidates that the attacker needs to try to recover the
key using exhaustive search?
b) If the attacker has 2 plaintext-ciphertext pairs chosen by themselves (not obtained from
known plaintext) and wants to use a chosen-plaintext attack, how many queries do they need to
make to uniquely determine the key?
Solution 4.
a) Since the key size is 128 bits, the total number of possible keys is 2128. With the given 10
plaintext-ciphertext pairs, the attacker needs to try each key candidate against all pairs. Therefore,
the maximum number of key candidates to try is 2128 = 340,282,366,920,938,463,463,374,607,431,768,211,456.
b) In a chosen-plaintext attack, the attacker can choose their plaintexts. With 2 plaintext-
ciphertext pairs, each pair contributes 64 bits of information about the key (block size). Since
the key size is 128 bits, the attacker needs a total of 128/64 = 2 pairs to uniquely determine the
key. Therefore, the attacker needs to make a total of 2 queries.
I. Problem:
Consider a side-channel attack on a symmetric encryption algorithm that leaks information
about the encryption key based on the power consumption during encryption. Suppose you have
the following data:
- Power consumption when encrypting the plaintext 0x45: 100 units - Power consumption when
encrypting the plaintext 0xAF: 150 units
Assume that the power consumption is directly related to the number of bit changes in the
encryption key during encryption.
a) Determine the Hamming distance (number of differing bits) between the encryption keys
used for encrypting the plaintexts 0x45 and 0xAF.
b) If the encryption key consists of 8 bits, find the average power consumption when encrypting
a plaintext using this encryption algorithm.
Solution:
a) To find the Hamming distance between the encryption keys used for the two plaintexts:
0x45 =0100 0101
0xAF =1010 1111
The Hamming distance is the number of bit positions in which the two binary strings differ:
Hamming distance = 3 (bits that differ are in positions 2, 5, and 7)
b) With an 8-bit key, each bit change contributes to the power consumption. From part a, we
calculated three differing bits in the encryption key. Thus, the average power consumption when
encrypting a plaintext is:
Average power consumption =Total power consumption
Number of bit changes =100+150
3=250
3≈83.33 units
Therefore, the average power consumption when encrypting a plaintext using this encryption
algorithm is approximately 83.33 units.
5 6. LACK OF PROTECTION AGAINST QUANTUM COMPUTING THREATS
Problem 6. Consider the Shor’s algorithm for integer factorization. Given N= 15, find the
prime factors of Nusing Shor’s algorithm.
Solution 6. a) According to Shor’s algorithm, we need to find the period of the function f(x) =
axmod N, where a= 2.
Let’s find the period:
•f(0) = 20mod 15 = 1
•f(1) = 21mod 15 = 2
•f(2) = 22mod 15 = 4
•f(3) = 23mod 15 = 8
•f(4) = 24mod 15 = 1
The smallest period is r= 4. We need to find a1= 2(r/2) mod 15. Since r= 4,a1= 22
mod 15 = 4.
Next, we solve the equation gcd(ar/2±1, N). Either gcd(4 + 1,15) or gcd(4 −1,15).
•gcd(5,15) = 5 is a factor of N.
Therefore, the prime factors of N= 15 are 5and 3.
Thus, the prime factors of Nare 3and 5.
b) In this part, we find the same prime factors of N= 15 using the general approach. We
factorize 15 to prime numbers: 15 = 3 ×5.
c) Compare the results obtained from Shor’s algorithm and the general approach.
The results from Shor’s algorithm (3and 5) and the general approach (3and 5) are the same,
confirming the accuracy of both methods.
6 7. RISK OF COLLUSION ATTACKS ON CRYPTOGRAPHIC SYSTEMS
Problem 7. Consider a cryptographic system that uses a key exchange protocol with npartic-
ipants. Each participant holds a secret key that is randomly generated. If kparticipants collude to
share their secret keys, what is the probability that the colluding participants can decrypt a message
encrypted using the system?
Assume that the system is secure as long as at least one participant’s key remains secret.
Solution 7.
To find the probability that the colluding participants can decrypt the message, we need to
calculate the probability that all kparticipants’ keys are shared.
Let’s denote the total number of participants as nand the number of colluding participants as
k. The probability that all kparticipants’ keys are shared can be calculated as follows:
a) Probability that the first participant’s key is shared: k
n
b) Probability that the second participant’s key is shared given that the first participant’s key is
shared: k−1
n−1
c) Probability that the k-th participant’s key is shared given that the previous k−1participants’
keys are shared: k−(k−1)
n−(k−1) =1
n−(k−1)
Therefore, the overall probability that all kparticipants’ keys are shared is:
P(All kkeys are shared) = k
n×k−1
n−1×. . . ×1
n−(k−1)
Substitute n= 10 and k= 3 into the formula:
P(All 3keys are shared) = 3
10 ×2
9×1
8=1
120
Therefore, the probability that the colluding participants can decrypt the message is 1
120 .
7 8. INSECURE RANDOM NUMBER GENERATION IN CRYPTOGRAPHIC ALGORITHMS
Problem 8. Consider a scenario where a cryptographic algorithm requires generating random
numbers for secure key generation. However, the random number generator used is insecure and
produces predictable outputs.
Assume the insecure random number generator outputs a sequence of numbers as follows: 4,
8, 12, 16, 20, 24, ...
a) Calculate the next three numbers that will be generated by this insecure random number
generator.
b) Explain why using such an insecure random number generator for cryptographic purposes
is problematic.
Solution 8.
a) The pattern observed in the sequence of numbers generated by the insecure random number
generator is incrementing by 4. Therefore, the next three numbers that will be generated are: - 28
- 32 - 36
b) Using an insecure random number generator for cryptographic purposes is problematic be-
cause it introduces predictability in generating cryptographic keys or other sensitive parameters.
If an attacker can predict the numbers being used to generate cryptographic keys, they may be
able to break the encryption scheme and compromise the security of the system. Randomness is
a crucial element in cryptographic protocols to ensure secure communication and protect sensitive
information.
8 9. WEAKNESSES IN HASH FUNCTIONS
Problem 9. Consider a hash function H(x)=(ax +b) mod 11, where a= 3 and b= 5.
a) Calculate H(7).
b) Find an input xsuch that H(x)=6.
c) Determine whether the given hash function is collision-resistant.
Solution 9.
a) To find H(7), substitute x= 7 into the hash function:
H(7) = (3 ·7 + 5) mod 11 = 26 mod 11 = 4
Therefore, H(7) = 4.
b) To find an input xsuch that H(x)=6, set H(x)=6and solve for x:
(3x+ 5) mod 11 = 6
3x+ 5 = 6 ·11 + k, where 0≤k < 11
3x+ 5 = 66 + k
3x= 61 + k
Since kcan take values from 0 to 10, we check for ksuch that (61 + k)is divisible by 3:
k= 1
3x= 62
x=62
3= 202
3
Therefore, an input xsuch that H(x)=6is not an integer.
c) The given hash function is not collision-resistant because multiple inputs can map to the
same output. For example, H(0) = 5 and H(11) = 5, showing a collision.
9 Cryptographic Algorithms and Protocols
Problem 1. Consider a digital signature scheme that uses the RSA algorithm with a modulus
N= 187 and public exponent e= 13. Alice signs a message by raising it to the power of d= 37
(mod 187). If the original message is m= 45, what is the signature that Alice sends?
Solution 1. Given that N= 187,e= 13,d= 37, and m= 45, we can calculate the signature
as follows:
1. Calculate the public key component:
public key = (N, e) = (187,13)
2. Calculate the private key component: Firstly, we need to find pand qsuch that N=p·q= 187.
Through factorization, we find that p= 11 and q= 17. Next, calculate ϕ(N) = (p−1)(q−1) =
10 ·16 = 160. Then, calculate the private key d=e−1(mod ϕ(N)).
d= 13−1(mod 160) = 37
3. Calculate the signature: The signature is calculated as:
signature =md(mod N) = 4537 (mod 187)
signature = 148
Therefore, Alice will send the signature 148 for the message m= 45.
10 11. ISSUES WITH SECURE MULTIPARTY COMPUTATION PROTOCOLS
Problem 11. Consider a secure multiparty computation protocol involving three parties A,B,
and C. Each party has a secret number that they want to compute the sum of without revealing
their individual values. The protocol involves additive secret sharing where each party splits their
secret into two shares and sends one share to each of the other parties. The sum of the three
secret numbers should be computed by combining the shares in a secure manner.
Suppose A’s secret share sent to Bis 5, B’s secret share sent to Cis 3, and C’s secret share
sent to Ais 7.
a) Determine the sum of the three secret numbers without revealing the individual secrets.
b) Discuss any potential security risks or attacks that could compromise the secrecy of the
computed sum.
Solution 11.
a) To compute the sum of the three secret numbers, we can add up all the shares sent between
the parties:
A’s share sent to B(5) + B’s share sent to C(3) + C’s share sent to A(7)=5+3+7=15
Therefore, the sum of the three secret numbers is 15.
b) One potential security risk is collusion between two parties. If two parties collude and share
their secret shares, they can deduce the third secret share and thus compromise the secrecy of
the computed sum. In this case, if Aand Ccollude, they can add their secret shares to obtain B’s
secret share without Bknowing. This would reveal B’s secret and compromise the security of the
protocol.
10.1 12. DIFFICULTY IN ACHIEVING FORWARD SECRECY IN COMMUNICATION
PROTOCOLS
Problem 12. In a communication protocol, Alice and Bob agreed to use the Diffie-Hellman key
exchange algorithm to establish a shared secret key. Alice’s public key is g= 5 and p= 23. Bob’s
public key is g= 7 and p= 23. Given that the secret key (afor Alice and bfor Bob) is 6and 12
respectively, calculate the shared secret key.
Solution 12.
a) Alice calculates (gbmod p)amod pto obtain the shared secret key:
Alice: (76mod 23)12 mod 23
Calculating the values:
(279936 mod 23)12 mod 23
1412 mod 23
1,116,668,081,822,284 mod 23
21
Therefore, the shared secret key for Alice is 21.
b) Bob calculates (gamod p)bmod pto obtain the shared secret key:
Bob: (512 mod 23)6mod 23
Calculating the values:
(244140625 mod 23)6mod 23
186mod 23
34,992,033,553 mod 23
15
Therefore, the shared secret key for Bob is 15.
c) Since both Alice and Bob have calculated their respective shared secret keys, they can now
communicate securely using the Diffie-Hellman key exchange algorithm with a shared key of 15.
I. Problems on Cryptographic Algorithms and Protocols
11 13. CHALLENGES IN IMPLEMENTING HOMOMORPHIC ENCRYPTION
Problem 13. Consider a homomorphic encryption scheme where plaintexts are encoded as
integers mod 26. The encryption function takes a plaintext mand two random numbers r1and
r2to generate the ciphertext: c=m+r1mod 26 + r2mod 26. Suppose we want to perform a
homomorphic multiplication operation on two ciphertexts c1and c2, where c1= 10 and c2= 17.
Calculate the result of the homomorphic multiplication operation.
Solution 13. To perform homomorphic multiplication, we can simply multiply the ciphertexts:
cmul =c1×c2mod 26. Given c1= 10 and c2= 17, we have:
cmul = 10 ×17 mod 26 = 170 mod 26 = 12
Therefore, the result of the homomorphic multiplication operation on ciphertexts c1= 10 and
c2= 17 is cmul = 12.
This concludes the solution to the problem.
12 Cryptographic Algorithms and Protocols
Problem 1. Consider a simple substitution cipher where each letter of the alphabet is replaced
by a different letter. If we have encrypted the message "HELLO" using a substitution cipher and the
encryption key is as follows: {H→Q, E →B, L →X, O →M}, what is the encrypted message?
Problem 2. Alice and Bob want to establish a shared secret key using the Diffie-Hellman key
exchange protocol. If the prime number p= 23 and the primitive root α= 5, Alice chooses her
private key as a= 6 and Bob chooses his private key as b= 15, what is the shared secret key that
they will both compute?
Problem 3. In RSA encryption, if the public key is (n= 77, e = 7) and the message to be
encrypted is m= 13, what is the ciphertext produced using the RSA algorithm?
Solution 1. a) The encrypted message for "HELLO" using the substitution cipher key given
would be "QBXXM".
b) Alice computes her public key as A=αamod p= 56mod 23 = 8. Bob computes his
public key as B=αbmod p= 515 mod 23 = 19. The shared secret key is K=Bamod p= 196
mod 23 = 2.
c) To encrypt the message using RSA encryption, compute c=memod n= 137mod 77 =
16. Therefore, the ciphertext produced is 16.
13 Cryptographic Algorithms and Protocols
Problem 1. Consider a secure communication protocol that uses Diffie-Hellman key exchange
to establish a shared secret key between Alice and Bob. If the prime modulus p= 23 and the base
g= 5, determine the shared secret key when Alice chooses a private key a= 6 and Bob chooses
a private key b= 15.
Solution 1. The shared secret key can be calculated by both Alice and Bob using the following
steps:
a) Alice calculates A=gamod p:
A= 56mod 23 = 25 mod 23 = 2
b) Bob calculates B=gbmod p:
B= 515 mod 23 = 30,517,578,125 mod 23 = 19
c) Alice and Bob share their calculated values Aand B, respectively.
d) Alice calculates the shared secret key: K=Bamod p:
K= 196mod 23 = 47,045,881 mod 23 = 2
e) Bob calculates the shared secret key: K=Abmod p:
K= 215 mod 23 = 32,768 mod 23 = 2
Thus, the shared secret key for both Alice and Bob is 2.
Problem 2. In the RSA encryption algorithm, suppose Alice chooses two prime numbers p= 11
and q= 17 for her public and private keys. She also chooses the public encryption exponent e= 7.
Determine the private decryption exponent d.
Solution 2. To find the private decryption exponent d, we must first calculate the following: -
n=p×q= 11 ×17 = 187 -φ(n)=(p−1) ×(q−1) = 10 ×16 = 160 - Then we solve the equation
e×d≡1 (mod φ(n)) for d:
7d≡1 (mod 160)
Solving this congruence equation, we find d= 23.
I’m happy to help with that. Here is a numerical problem on Cryptographic Algorithms and
Protocols for you:
14 16. PROBLEMS WITH END-TO-END ENCRYPTION SOLUTIONS
Problem 16. Consider a scenario where Alice wants to securely communicate with Bob using end-
to-end encryption. They decide to use the RSA cryptosystem for encryption and decryption. Alice’s
public key is (eA, NA) = (5,143), and her private key is (dA, NA) = (29,143). Bob generates his
own keys where his public key is (eB, NB) = (3,187), and his private key is (dB, NB) = (107,187).
a) If Alice wants to send a message M = 25 to Bob, what is the ciphertext that will be sent over
the network?
b) If Bob receives the ciphertext C = 97 from Alice, what is the original message M that Alice
intended to send him?
Solution 16.
a) To encrypt the message M = 25 using Alice’s public key, we use the encryption function:
C=MeAmod NA
C= 255mod 143
C= 3125 mod 143
C= 49
Therefore, the ciphertext that will be sent over the network is 49.
b) To decrypt the ciphertext C = 97 using Bob’s private key, we use the decryption function:
M=CdBmod NB
M= 97107 mod 187
M= 136904183893900215547781596700000000000000000000000000000000000000000000000000000000000000000 < /br > mod 187
M= 25
Therefore, the original message that Alice intended to send to Bob is 25.
15 17. CHALLENGES IN ACHIEVING SECURE AUTHENTICATION IN DISTRIBUTED SYS-
TEMS
Problem 17. Consider a distributed system where three entities need to authenticate each other
using a challenge-response protocol based on a shared secret key. Entity Agenerates a random
challenge cA= 347, Entity Bgenerates a random challenge cB= 512, and Entity Cgenerates a
random challenge cC= 635. The shared secret key between all entities is K= 123.
a) Entity Asends cAto Entity B, who responds with the result of cA⊕K. Calculate the response
sent by Entity Bto Entity A.
b) Entity Bsends cBto Entity C, who responds with the result of cB⊕K. Calculate the response
sent by Entity Cto Entity B.
c) Entity Csends cCto Entity A, who responds with the result of cC⊕K. Calculate the response
sent by Entity Ato Entity C.
Solution 17.
a) Entity Bcalculates the response as cA⊕K:
cA⊕K= 347 ⊕123 = 224
Therefore, Entity Bsends the response 224 to Entity A.
b) Entity Ccalculates the response as cB⊕K:
cB⊕K= 512 ⊕123 = 635
Therefore, Entity Csends the response 635 to Entity B.
c) Entity Acalculates the response as cC⊕K:
cC⊕K= 635 ⊕123 = 756
Therefore, Entity Asends the response 756 to Entity C.
16 Cryptographic Algorithms and Protocols
Problem: Alice wants to securely send a message to Bob using symmetric encryption. She
chooses the block cipher AES with a key size of 128 bits. The message she wants to send is 1280
bits long.
a) How many blocks will the message be divided into for encryption using AES?
b) If Alice and Bob are using the Electronic Code Book (ECB) mode, explain what kind of
vulnerability may arise in this scenario.
Solution:
a) The AES block size is 128 bits (16 bytes), so the 1280-bit message will need to be divided
into blocks of size 128 bits each.
Number of blocks = Message size / Block size = 1280 bits / 128 bits = 10 blocks
Therefore, the message will be divided into 10 blocks for encryption using AES.
b) In the ECB mode, each block of plaintext is encrypted separately with the same key. This
means that identical plaintext blocks will result in identical ciphertext blocks. This vulnerability can
be exploited by an attacker to detect patterns in the encrypted data, potentially revealing information
or relationships within the message. Additionally, ECB does not provide semantic security, so it
may leak information even if the plaintext is encrypted.
In the given scenario, if Alice sends any message that contains repeated blocks of plaintext
(e.g., patterns, images, or repeated phrases), an attacker can identify these repetitions and poten-
tially infer information about the message’s content.
I am unable to provide numerical problem questions and solutions for Cryptographic Algorithms
and Protocols at the moment. Would you like me to assist you with theoretical concepts or any other
form of assistance related to this topic?
I can certainly provide a problem and solution for you!
17 Cryptographic Algorithms and Protocols
Problem:
Consider the following scenario in a public-key encryption system using RSA:
Alice wants to send a confidential message to Bob. Bob has a public encryption key (e, n) =
(17,323) and a private key (d, n) = (275,323). Alice encrypts her message as follows: she repre-
sents the message as a number where each letter is assigned a value (A=1, B=2, ..., Z=26), and
then raises this number to the power of the public key (e)modulo nto obtain the ciphertext.
Alice’s message is "HELLO". The numerical representation of this message is [8, 5, 12, 12,
15]. Calculate the ciphertext that Alice will send to Bob.
Solution:
To find the ciphertext for the message "HELLO", we will encrypt each letter separately and
combine the results.
Let’s encode each letter:
H: 8 E: 5 L: 12 L: 12 O: 15
For letter "H": 817 ≡106 (mod 323)
For letter "E": 517 ≡9 (mod 323)
For letter "L": 1217 ≡144 (mod 323)
For the second "L": 1217 ≡144 (mod 323)
For letter "O": 1517 ≡21 (mod 323)
Now, combine these ciphertext values: 1069194144214421
Therefore, the ciphertext that Alice will send to Bob for the message "HELLO" is 10691941442144.
3 3. VULNERABILITIES IN ASYMMETRIC ENCRYPTION SCHEMES
Problem 3. Consider the RSA encryption scheme with public key (e, N) = (7,187). An attacker
intercepts a message m= 65 encrypted using this public key.
a) Compute the private key d.
b) Determine the decrypted message.
Solution 3.
a) To compute the private key d, we need to find the value such that ed ≡1 (mod φ(N)), where
φ(N)is Euler’s totient function.
Given that N= 187, we first need to calculate φ(N):
φ(N)=(p−1)(q−1) = 10 ×18 = 180.
Next, we solve for d:
7d≡1 (mod 180).
Solving this congruence, we get d= 103.
b) To decrypt the message, we calculate cd(mod N), where cis the intercepted ciphertext.
m= 65103 (mod 187).
Using fast modular exponentiation, we can simplify this calculation:
652≡52 (mod 187),
654≡522≡64 (mod 187),
658≡642≡141 (mod 187),
6516 ≡1412≡145 (mod 187),
6532 ≡1452≡79 (mod 187),
6564 ≡792≡77 (mod 187).
Therefore,
65103 ≡65 ×6532 ×6516 ×652×651
≡65 ×79 ×145 ×52
≡64 (mod 187).
Hence, the decrypted message is m= 64.
4 4. CRYPTANALYSIS OF SYMMETRIC KEY ALGORITHMS
Problem 4. Consider a block cipher with a block size of 64 bits and a key size of 128 bits. An
attacker performs a known-plaintext attack where they obtain 10 plaintext-ciphertext pairs. Each
pair has a plaintext of 64 bits and a corresponding ciphertext of 64 bits. The attacker wants to
determine the key using this information.
a) What is the maximum number of key candidates that the attacker needs to try to recover the
key using exhaustive search?
b) If the attacker has 2 plaintext-ciphertext pairs chosen by themselves (not obtained from
known plaintext) and wants to use a chosen-plaintext attack, how many queries do they need to
make to uniquely determine the key?
Solution 4.
a) Since the key size is 128 bits, the total number of possible keys is 2128. With the given 10
plaintext-ciphertext pairs, the attacker needs to try each key candidate against all pairs. Therefore,
the maximum number of key candidates to try is 2128 = 340,282,366,920,938,463,463,374,607,431,768,211,456.
b) In a chosen-plaintext attack, the attacker can choose their plaintexts. With 2 plaintext-
ciphertext pairs, each pair contributes 64 bits of information about the key (block size). Since
the key size is 128 bits, the attacker needs a total of 128/64 = 2 pairs to uniquely determine the
key. Therefore, the attacker needs to make a total of 2 queries.
I. Problem:
Consider a side-channel attack on a symmetric encryption algorithm that leaks information
about the encryption key based on the power consumption during encryption. Suppose you have
the following data:
- Power consumption when encrypting the plaintext 0x45: 100 units - Power consumption when
encrypting the plaintext 0xAF: 150 units
Assume that the power consumption is directly related to the number of bit changes in the
encryption key during encryption.
a) Determine the Hamming distance (number of differing bits) between the encryption keys
used for encrypting the plaintexts 0x45 and 0xAF.
b) If the encryption key consists of 8 bits, find the average power consumption when encrypting
a plaintext using this encryption algorithm.
Solution:
a) To find the Hamming distance between the encryption keys used for the two plaintexts:
0x45 =0100 0101
0xAF =1010 1111
The Hamming distance is the number of bit positions in which the two binary strings differ:
Hamming distance = 3 (bits that differ are in positions 2, 5, and 7)
b) With an 8-bit key, each bit change contributes to the power consumption. From part a, we
calculated three differing bits in the encryption key. Thus, the average power consumption when
encrypting a plaintext is:
Average power consumption =Total power consumption
Number of bit changes =100+150
3=250
3≈83.33 units
Therefore, the average power consumption when encrypting a plaintext using this encryption
algorithm is approximately 83.33 units.
5 6. LACK OF PROTECTION AGAINST QUANTUM COMPUTING THREATS
Problem 6. Consider the Shor’s algorithm for integer factorization. Given N= 15, find the
prime factors of Nusing Shor’s algorithm.
Solution 6. a) According to Shor’s algorithm, we need to find the period of the function f(x) =
axmod N, where a= 2.
Let’s find the period:
•f(0) = 20mod 15 = 1
•f(1) = 21mod 15 = 2
•f(2) = 22mod 15 = 4
•f(3) = 23mod 15 = 8
•f(4) = 24mod 15 = 1
The smallest period is r= 4. We need to find a1= 2(r/2) mod 15. Since r= 4,a1= 22
mod 15 = 4.
Next, we solve the equation gcd(ar/2±1, N). Either gcd(4 + 1,15) or gcd(4 −1,15).
•gcd(5,15) = 5 is a factor of N.
Therefore, the prime factors of N= 15 are 5and 3.
Thus, the prime factors of Nare 3and 5.
b) In this part, we find the same prime factors of N= 15 using the general approach. We
factorize 15 to prime numbers: 15 = 3 ×5.
c) Compare the results obtained from Shor’s algorithm and the general approach.
The results from Shor’s algorithm (3and 5) and the general approach (3and 5) are the same,
confirming the accuracy of both methods.
6 7. RISK OF COLLUSION ATTACKS ON CRYPTOGRAPHIC SYSTEMS
Problem 7. Consider a cryptographic system that uses a key exchange protocol with npartic-
ipants. Each participant holds a secret key that is randomly generated. If kparticipants collude to
share their secret keys, what is the probability that the colluding participants can decrypt a message
encrypted using the system?
Assume that the system is secure as long as at least one participant’s key remains secret.
Solution 7.
To find the probability that the colluding participants can decrypt the message, we need to
calculate the probability that all kparticipants’ keys are shared.
Let’s denote the total number of participants as nand the number of colluding participants as
k. The probability that all kparticipants’ keys are shared can be calculated as follows:
a) Probability that the first participant’s key is shared: k
n
b) Probability that the second participant’s key is shared given that the first participant’s key is
shared: k−1
n−1
c) Probability that the k-th participant’s key is shared given that the previous k−1participants’
keys are shared: k−(k−1)
n−(k−1) =1
n−(k−1)
Therefore, the overall probability that all kparticipants’ keys are shared is:
P(All kkeys are shared) = k
n×k−1
n−1×. . . ×1
n−(k−1)
Substitute n= 10 and k= 3 into the formula:
P(All 3keys are shared) = 3
10 ×2
9×1
8=1
120
Therefore, the probability that the colluding participants can decrypt the message is 1
120 .
7 8. INSECURE RANDOM NUMBER GENERATION IN CRYPTOGRAPHIC ALGORITHMS
Problem 8. Consider a scenario where a cryptographic algorithm requires generating random
numbers for secure key generation. However, the random number generator used is insecure and
produces predictable outputs.
Assume the insecure random number generator outputs a sequence of numbers as follows: 4,
8, 12, 16, 20, 24, ...
a) Calculate the next three numbers that will be generated by this insecure random number
generator.
b) Explain why using such an insecure random number generator for cryptographic purposes
is problematic.
Solution 8.
a) The pattern observed in the sequence of numbers generated by the insecure random number
generator is incrementing by 4. Therefore, the next three numbers that will be generated are: - 28
- 32 - 36
b) Using an insecure random number generator for cryptographic purposes is problematic be-
cause it introduces predictability in generating cryptographic keys or other sensitive parameters.
If an attacker can predict the numbers being used to generate cryptographic keys, they may be
able to break the encryption scheme and compromise the security of the system. Randomness is
a crucial element in cryptographic protocols to ensure secure communication and protect sensitive
information.
8 9. WEAKNESSES IN HASH FUNCTIONS
Problem 9. Consider a hash function H(x)=(ax +b) mod 11, where a= 3 and b= 5.
a) Calculate H(7).
b) Find an input xsuch that H(x)=6.
c) Determine whether the given hash function is collision-resistant.
Solution 9.
a) To find H(7), substitute x= 7 into the hash function:
H(7) = (3 ·7 + 5) mod 11 = 26 mod 11 = 4
Therefore, H(7) = 4.
b) To find an input xsuch that H(x)=6, set H(x)=6and solve for x:
(3x+ 5) mod 11 = 6
3x+ 5 = 6 ·11 + k, where 0≤k < 11
3x+ 5 = 66 + k
3x= 61 + k
Since kcan take values from 0 to 10, we check for ksuch that (61 + k)is divisible by 3:
k= 1
3x= 62
x=62
3= 202
3
Therefore, an input xsuch that H(x)=6is not an integer.
c) The given hash function is not collision-resistant because multiple inputs can map to the
same output. For example, H(0) = 5 and H(11) = 5, showing a collision.
9 Cryptographic Algorithms and Protocols
Problem 1. Consider a digital signature scheme that uses the RSA algorithm with a modulus
N= 187 and public exponent e= 13. Alice signs a message by raising it to the power of d= 37
(mod 187). If the original message is m= 45, what is the signature that Alice sends?
Solution 1. Given that N= 187,e= 13,d= 37, and m= 45, we can calculate the signature
as follows:
1. Calculate the public key component:
public key = (N, e) = (187,13)
2. Calculate the private key component: Firstly, we need to find pand qsuch that N=p·q= 187.
Through factorization, we find that p= 11 and q= 17. Next, calculate ϕ(N) = (p−1)(q−1) =
10 ·16 = 160. Then, calculate the private key d=e−1(mod ϕ(N)).
d= 13−1(mod 160) = 37
3. Calculate the signature: The signature is calculated as:
signature =md(mod N) = 4537 (mod 187)
signature = 148
Therefore, Alice will send the signature 148 for the message m= 45.
10 11. ISSUES WITH SECURE MULTIPARTY COMPUTATION PROTOCOLS
Problem 11. Consider a secure multiparty computation protocol involving three parties A,B,
and C. Each party has a secret number that they want to compute the sum of without revealing
their individual values. The protocol involves additive secret sharing where each party splits their
secret into two shares and sends one share to each of the other parties. The sum of the three
secret numbers should be computed by combining the shares in a secure manner.
Suppose A’s secret share sent to Bis 5, B’s secret share sent to Cis 3, and C’s secret share
sent to Ais 7.
a) Determine the sum of the three secret numbers without revealing the individual secrets.
b) Discuss any potential security risks or attacks that could compromise the secrecy of the
computed sum.
Solution 11.
a) To compute the sum of the three secret numbers, we can add up all the shares sent between
the parties:
A’s share sent to B(5) + B’s share sent to C(3) + C’s share sent to A(7)=5+3+7=15
Therefore, the sum of the three secret numbers is 15.
b) One potential security risk is collusion between two parties. If two parties collude and share
their secret shares, they can deduce the third secret share and thus compromise the secrecy of
the computed sum. In this case, if Aand Ccollude, they can add their secret shares to obtain B’s
secret share without Bknowing. This would reveal B’s secret and compromise the security of the
protocol.
10.1 12. DIFFICULTY IN ACHIEVING FORWARD SECRECY IN COMMUNICATION
PROTOCOLS
Problem 12. In a communication protocol, Alice and Bob agreed to use the Diffie-Hellman key
exchange algorithm to establish a shared secret key. Alice’s public key is g= 5 and p= 23. Bob’s
public key is g= 7 and p= 23. Given that the secret key (afor Alice and bfor Bob) is 6and 12
respectively, calculate the shared secret key.
Solution 12.
a) Alice calculates (gbmod p)amod pto obtain the shared secret key:
Alice: (76mod 23)12 mod 23
Calculating the values:
(279936 mod 23)12 mod 23
1412 mod 23
1,116,668,081,822,284 mod 23
21
Therefore, the shared secret key for Alice is 21.
b) Bob calculates (gamod p)bmod pto obtain the shared secret key:
Bob: (512 mod 23)6mod 23
Calculating the values:
(244140625 mod 23)6mod 23
186mod 23
34,992,033,553 mod 23
15
Therefore, the shared secret key for Bob is 15.
c) Since both Alice and Bob have calculated their respective shared secret keys, they can now
communicate securely using the Diffie-Hellman key exchange algorithm with a shared key of 15.
I. Problems on Cryptographic Algorithms and Protocols
11 13. CHALLENGES IN IMPLEMENTING HOMOMORPHIC ENCRYPTION
Problem 13. Consider a homomorphic encryption scheme where plaintexts are encoded as
integers mod 26. The encryption function takes a plaintext mand two random numbers r1and
r2to generate the ciphertext: c=m+r1mod 26 + r2mod 26. Suppose we want to perform a
homomorphic multiplication operation on two ciphertexts c1and c2, where c1= 10 and c2= 17.
Calculate the result of the homomorphic multiplication operation.
Solution 13. To perform homomorphic multiplication, we can simply multiply the ciphertexts:
cmul =c1×c2mod 26. Given c1= 10 and c2= 17, we have:
cmul = 10 ×17 mod 26 = 170 mod 26 = 12
Therefore, the result of the homomorphic multiplication operation on ciphertexts c1= 10 and
c2= 17 is cmul = 12.
This concludes the solution to the problem.
12 Cryptographic Algorithms and Protocols
Problem 1. Consider a simple substitution cipher where each letter of the alphabet is replaced
by a different letter. If we have encrypted the message "HELLO" using a substitution cipher and the
encryption key is as follows: {H→Q, E →B, L →X, O →M}, what is the encrypted message?
Problem 2. Alice and Bob want to establish a shared secret key using the Diffie-Hellman key
exchange protocol. If the prime number p= 23 and the primitive root α= 5, Alice chooses her
private key as a= 6 and Bob chooses his private key as b= 15, what is the shared secret key that
they will both compute?
Problem 3. In RSA encryption, if the public key is (n= 77, e = 7) and the message to be
encrypted is m= 13, what is the ciphertext produced using the RSA algorithm?
Solution 1. a) The encrypted message for "HELLO" using the substitution cipher key given
would be "QBXXM".
b) Alice computes her public key as A=αamod p= 56mod 23 = 8. Bob computes his
public key as B=αbmod p= 515 mod 23 = 19. The shared secret key is K=Bamod p= 196
mod 23 = 2.
c) To encrypt the message using RSA encryption, compute c=memod n= 137mod 77 =
16. Therefore, the ciphertext produced is 16.
13 Cryptographic Algorithms and Protocols
Problem 1. Consider a secure communication protocol that uses Diffie-Hellman key exchange
to establish a shared secret key between Alice and Bob. If the prime modulus p= 23 and the base
g= 5, determine the shared secret key when Alice chooses a private key a= 6 and Bob chooses
a private key b= 15.
Solution 1. The shared secret key can be calculated by both Alice and Bob using the following
steps:
a) Alice calculates A=gamod p:
A= 56mod 23 = 25 mod 23 = 2
b) Bob calculates B=gbmod p:
B= 515 mod 23 = 30,517,578,125 mod 23 = 19
c) Alice and Bob share their calculated values Aand B, respectively.
d) Alice calculates the shared secret key: K=Bamod p:
K= 196mod 23 = 47,045,881 mod 23 = 2
e) Bob calculates the shared secret key: K=Abmod p:
K= 215 mod 23 = 32,768 mod 23 = 2
Thus, the shared secret key for both Alice and Bob is 2.
Problem 2. In the RSA encryption algorithm, suppose Alice chooses two prime numbers p= 11
and q= 17 for her public and private keys. She also chooses the public encryption exponent e= 7.
Determine the private decryption exponent d.
Solution 2. To find the private decryption exponent d, we must first calculate the following: -
n=p×q= 11 ×17 = 187 -φ(n)=(p−1) ×(q−1) = 10 ×16 = 160 - Then we solve the equation
e×d≡1 (mod φ(n)) for d:
7d≡1 (mod 160)
Solving this congruence equation, we find d= 23.
I’m happy to help with that. Here is a numerical problem on Cryptographic Algorithms and
Protocols for you:
14 16. PROBLEMS WITH END-TO-END ENCRYPTION SOLUTIONS
Problem 16. Consider a scenario where Alice wants to securely communicate with Bob using end-
to-end encryption. They decide to use the RSA cryptosystem for encryption and decryption. Alice’s
public key is (eA, NA) = (5,143), and her private key is (dA, NA) = (29,143). Bob generates his
own keys where his public key is (eB, NB) = (3,187), and his private key is (dB, NB) = (107,187).
a) If Alice wants to send a message M = 25 to Bob, what is the ciphertext that will be sent over
the network?
b) If Bob receives the ciphertext C = 97 from Alice, what is the original message M that Alice
intended to send him?
Solution 16.
a) To encrypt the message M = 25 using Alice’s public key, we use the encryption function:
C=MeAmod NA
C= 255mod 143
C= 3125 mod 143
C= 49
Therefore, the ciphertext that will be sent over the network is 49.
b) To decrypt the ciphertext C = 97 using Bob’s private key, we use the decryption function:
M=CdBmod NB
M= 97107 mod 187
M= 136904183893900215547781596700000000000000000000000000000000000000000000000000000000000000000 < /br > mod 187
M= 25
Therefore, the original message that Alice intended to send to Bob is 25.
15 17. CHALLENGES IN ACHIEVING SECURE AUTHENTICATION IN DISTRIBUTED SYS-
TEMS
Problem 17. Consider a distributed system where three entities need to authenticate each other
using a challenge-response protocol based on a shared secret key. Entity Agenerates a random
challenge cA= 347, Entity Bgenerates a random challenge cB= 512, and Entity Cgenerates a
random challenge cC= 635. The shared secret key between all entities is K= 123.
a) Entity Asends cAto Entity B, who responds with the result of cA⊕K. Calculate the response
sent by Entity Bto Entity A.
b) Entity Bsends cBto Entity C, who responds with the result of cB⊕K. Calculate the response
sent by Entity Cto Entity B.
c) Entity Csends cCto Entity A, who responds with the result of cC⊕K. Calculate the response
sent by Entity Ato Entity C.
Solution 17.
a) Entity Bcalculates the response as cA⊕K:
cA⊕K= 347 ⊕123 = 224
Therefore, Entity Bsends the response 224 to Entity A.
b) Entity Ccalculates the response as cB⊕K:
cB⊕K= 512 ⊕123 = 635
Therefore, Entity Csends the response 635 to Entity B.
c) Entity Acalculates the response as cC⊕K:
cC⊕K= 635 ⊕123 = 756
Therefore, Entity Asends the response 756 to Entity C.
16 Cryptographic Algorithms and Protocols
Problem: Alice wants to securely send a message to Bob using symmetric encryption. She
chooses the block cipher AES with a key size of 128 bits. The message she wants to send is 1280
bits long.
a) How many blocks will the message be divided into for encryption using AES?
b) If Alice and Bob are using the Electronic Code Book (ECB) mode, explain what kind of
vulnerability may arise in this scenario.
Solution:
a) The AES block size is 128 bits (16 bytes), so the 1280-bit message will need to be divided
into blocks of size 128 bits each.
Number of blocks = Message size / Block size = 1280 bits / 128 bits = 10 blocks
Therefore, the message will be divided into 10 blocks for encryption using AES.
b) In the ECB mode, each block of plaintext is encrypted separately with the same key. This
means that identical plaintext blocks will result in identical ciphertext blocks. This vulnerability can
be exploited by an attacker to detect patterns in the encrypted data, potentially revealing information
or relationships within the message. Additionally, ECB does not provide semantic security, so it
may leak information even if the plaintext is encrypted.
In the given scenario, if Alice sends any message that contains repeated blocks of plaintext
(e.g., patterns, images, or repeated phrases), an attacker can identify these repetitions and poten-
tially infer information about the message’s content.
I am unable to provide numerical problem questions and solutions for Cryptographic Algorithms
and Protocols at the moment. Would you like me to assist you with theoretical concepts or any other
form of assistance related to this topic?
I can certainly provide a problem and solution for you!
17 Cryptographic Algorithms and Protocols
Problem:
Consider the following scenario in a public-key encryption system using RSA:
Alice wants to send a confidential message to Bob. Bob has a public encryption key (e, n) =
(17,323) and a private key (d, n) = (275,323). Alice encrypts her message as follows: she repre-
sents the message as a number where each letter is assigned a value (A=1, B=2, ..., Z=26), and
then raises this number to the power of the public key (e)modulo nto obtain the ciphertext.
Alice’s message is "HELLO". The numerical representation of this message is [8, 5, 12, 12,
15]. Calculate the ciphertext that Alice will send to Bob.
Solution:
To find the ciphertext for the message "HELLO", we will encrypt each letter separately and
combine the results.
Let’s encode each letter:
H: 8 E: 5 L: 12 L: 12 O: 15
For letter "H": 817 ≡106 (mod 323)
For letter "E": 517 ≡9 (mod 323)
For letter "L": 1217 ≡144 (mod 323)
For the second "L": 1217 ≡144 (mod 323)
For letter "O": 1517 ≡21 (mod 323)
Now, combine these ciphertext values: 1069194144214421
Therefore, the ciphertext that Alice will send to Bob for the message "HELLO" is 10691941442144.
3 3. VULNERABILITIES IN ASYMMETRIC ENCRYPTION SCHEMES
Problem 3. Consider the RSA encryption scheme with public key (e, N) = (7,187). An attacker
intercepts a message m= 65 encrypted using this public key.
a) Compute the private key d.
b) Determine the decrypted message.
Solution 3.
a) To compute the private key d, we need to find the value such that ed ≡1 (mod φ(N)), where
φ(N)is Euler’s totient function.
Given that N= 187, we first need to calculate φ(N):
φ(N)=(p−1)(q−1) = 10 ×18 = 180.
Next, we solve for d:
7d≡1 (mod 180).
Solving this congruence, we get d= 103.
b) To decrypt the message, we calculate cd(mod N), where cis the intercepted ciphertext.
m= 65103 (mod 187).
Using fast modular exponentiation, we can simplify this calculation:
652≡52 (mod 187),
654≡522≡64 (mod 187),
658≡642≡141 (mod 187),
6516 ≡1412≡145 (mod 187),
6532 ≡1452≡79 (mod 187),
6564 ≡792≡77 (mod 187).
Therefore,
65103 ≡65 ×6532 ×6516 ×652×651
≡65 ×79 ×145 ×52
≡64 (mod 187).
Hence, the decrypted message is m= 64.
4 4. CRYPTANALYSIS OF SYMMETRIC KEY ALGORITHMS
Problem 4. Consider a block cipher with a block size of 64 bits and a key size of 128 bits. An
attacker performs a known-plaintext attack where they obtain 10 plaintext-ciphertext pairs. Each
pair has a plaintext of 64 bits and a corresponding ciphertext of 64 bits. The attacker wants to
determine the key using this information.
a) What is the maximum number of key candidates that the attacker needs to try to recover the
key using exhaustive search?
b) If the attacker has 2 plaintext-ciphertext pairs chosen by themselves (not obtained from
known plaintext) and wants to use a chosen-plaintext attack, how many queries do they need to
make to uniquely determine the key?
Solution 4.
a) Since the key size is 128 bits, the total number of possible keys is 2128. With the given 10
plaintext-ciphertext pairs, the attacker needs to try each key candidate against all pairs. Therefore,
the maximum number of key candidates to try is 2128 = 340,282,366,920,938,463,463,374,607,431,768,211,456.
b) In a chosen-plaintext attack, the attacker can choose their plaintexts. With 2 plaintext-
ciphertext pairs, each pair contributes 64 bits of information about the key (block size). Since
the key size is 128 bits, the attacker needs a total of 128/64 = 2 pairs to uniquely determine the
key. Therefore, the attacker needs to make a total of 2 queries.
I. Problem:
Consider a side-channel attack on a symmetric encryption algorithm that leaks information
about the encryption key based on the power consumption during encryption. Suppose you have
the following data:
- Power consumption when encrypting the plaintext 0x45: 100 units - Power consumption when
encrypting the plaintext 0xAF: 150 units
Assume that the power consumption is directly related to the number of bit changes in the
encryption key during encryption.
a) Determine the Hamming distance (number of differing bits) between the encryption keys
used for encrypting the plaintexts 0x45 and 0xAF.
b) If the encryption key consists of 8 bits, find the average power consumption when encrypting
a plaintext using this encryption algorithm.
Solution:
a) To find the Hamming distance between the encryption keys used for the two plaintexts:
0x45 =0100 0101
0xAF =1010 1111
The Hamming distance is the number of bit positions in which the two binary strings differ:
Hamming distance = 3 (bits that differ are in positions 2, 5, and 7)
b) With an 8-bit key, each bit change contributes to the power consumption. From part a, we
calculated three differing bits in the encryption key. Thus, the average power consumption when
encrypting a plaintext is:
Average power consumption =Total power consumption
Number of bit changes =100+150
3=250
3≈83.33 units
Therefore, the average power consumption when encrypting a plaintext using this encryption
algorithm is approximately 83.33 units.
5 6. LACK OF PROTECTION AGAINST QUANTUM COMPUTING THREATS
Problem 6. Consider the Shor’s algorithm for integer factorization. Given N= 15, find the
prime factors of Nusing Shor’s algorithm.
Solution 6. a) According to Shor’s algorithm, we need to find the period of the function f(x) =
axmod N, where a= 2.
Let’s find the period:
•f(0) = 20mod 15 = 1
•f(1) = 21mod 15 = 2
•f(2) = 22mod 15 = 4
•f(3) = 23mod 15 = 8
•f(4) = 24mod 15 = 1
The smallest period is r= 4. We need to find a1= 2(r/2) mod 15. Since r= 4,a1= 22
mod 15 = 4.
Next, we solve the equation gcd(ar/2±1, N). Either gcd(4 + 1,15) or gcd(4 −1,15).
•gcd(5,15) = 5 is a factor of N.
Therefore, the prime factors of N= 15 are 5and 3.
Thus, the prime factors of Nare 3and 5.
b) In this part, we find the same prime factors of N= 15 using the general approach. We
factorize 15 to prime numbers: 15 = 3 ×5.
c) Compare the results obtained from Shor’s algorithm and the general approach.
The results from Shor’s algorithm (3and 5) and the general approach (3and 5) are the same,
confirming the accuracy of both methods.
6 7. RISK OF COLLUSION ATTACKS ON CRYPTOGRAPHIC SYSTEMS
Problem 7. Consider a cryptographic system that uses a key exchange protocol with npartic-
ipants. Each participant holds a secret key that is randomly generated. If kparticipants collude to
share their secret keys, what is the probability that the colluding participants can decrypt a message
encrypted using the system?
Assume that the system is secure as long as at least one participant’s key remains secret.
Solution 7.
To find the probability that the colluding participants can decrypt the message, we need to
calculate the probability that all kparticipants’ keys are shared.
Let’s denote the total number of participants as nand the number of colluding participants as
k. The probability that all kparticipants’ keys are shared can be calculated as follows:
a) Probability that the first participant’s key is shared: k
n
b) Probability that the second participant’s key is shared given that the first participant’s key is
shared: k−1
n−1
c) Probability that the k-th participant’s key is shared given that the previous k−1participants’
keys are shared: k−(k−1)
n−(k−1) =1
n−(k−1)
Therefore, the overall probability that all kparticipants’ keys are shared is:
P(All kkeys are shared) = k
n×k−1
n−1×. . . ×1
n−(k−1)
Substitute n= 10 and k= 3 into the formula:
P(All 3keys are shared) = 3
10 ×2
9×1
8=1
120
Therefore, the probability that the colluding participants can decrypt the message is 1
120 .
7 8. INSECURE RANDOM NUMBER GENERATION IN CRYPTOGRAPHIC ALGORITHMS
Problem 8. Consider a scenario where a cryptographic algorithm requires generating random
numbers for secure key generation. However, the random number generator used is insecure and
produces predictable outputs.
Assume the insecure random number generator outputs a sequence of numbers as follows: 4,
8, 12, 16, 20, 24, ...
a) Calculate the next three numbers that will be generated by this insecure random number
generator.
b) Explain why using such an insecure random number generator for cryptographic purposes
is problematic.
Solution 8.
a) The pattern observed in the sequence of numbers generated by the insecure random number
generator is incrementing by 4. Therefore, the next three numbers that will be generated are: - 28
- 32 - 36
b) Using an insecure random number generator for cryptographic purposes is problematic be-
cause it introduces predictability in generating cryptographic keys or other sensitive parameters.
If an attacker can predict the numbers being used to generate cryptographic keys, they may be
able to break the encryption scheme and compromise the security of the system. Randomness is
a crucial element in cryptographic protocols to ensure secure communication and protect sensitive
information.
8 9. WEAKNESSES IN HASH FUNCTIONS
Problem 9. Consider a hash function H(x)=(ax +b) mod 11, where a= 3 and b= 5.
a) Calculate H(7).
b) Find an input xsuch that H(x)=6.
c) Determine whether the given hash function is collision-resistant.
Solution 9.
a) To find H(7), substitute x= 7 into the hash function:
H(7) = (3 ·7 + 5) mod 11 = 26 mod 11 = 4
Therefore, H(7) = 4.
b) To find an input xsuch that H(x)=6, set H(x)=6and solve for x:
(3x+ 5) mod 11 = 6
3x+ 5 = 6 ·11 + k, where 0≤k < 11
3x+ 5 = 66 + k
3x= 61 + k
Since kcan take values from 0 to 10, we check for ksuch that (61 + k)is divisible by 3:
k= 1
3x= 62
x=62
3= 202
3
Therefore, an input xsuch that H(x)=6is not an integer.
c) The given hash function is not collision-resistant because multiple inputs can map to the
same output. For example, H(0) = 5 and H(11) = 5, showing a collision.
9 Cryptographic Algorithms and Protocols
Problem 1. Consider a digital signature scheme that uses the RSA algorithm with a modulus
N= 187 and public exponent e= 13. Alice signs a message by raising it to the power of d= 37
(mod 187). If the original message is m= 45, what is the signature that Alice sends?
Solution 1. Given that N= 187,e= 13,d= 37, and m= 45, we can calculate the signature
as follows:
1. Calculate the public key component:
public key = (N, e) = (187,13)
2. Calculate the private key component: Firstly, we need to find pand qsuch that N=p·q= 187.
Through factorization, we find that p= 11 and q= 17. Next, calculate ϕ(N) = (p−1)(q−1) =
10 ·16 = 160. Then, calculate the private key d=e−1(mod ϕ(N)).
d= 13−1(mod 160) = 37
3. Calculate the signature: The signature is calculated as:
signature =md(mod N) = 4537 (mod 187)
signature = 148
Therefore, Alice will send the signature 148 for the message m= 45.
10 11. ISSUES WITH SECURE MULTIPARTY COMPUTATION PROTOCOLS
Problem 11. Consider a secure multiparty computation protocol involving three parties A,B,
and C. Each party has a secret number that they want to compute the sum of without revealing
their individual values. The protocol involves additive secret sharing where each party splits their
secret into two shares and sends one share to each of the other parties. The sum of the three
secret numbers should be computed by combining the shares in a secure manner.
Suppose A’s secret share sent to Bis 5, B’s secret share sent to Cis 3, and C’s secret share
sent to Ais 7.
a) Determine the sum of the three secret numbers without revealing the individual secrets.
b) Discuss any potential security risks or attacks that could compromise the secrecy of the
computed sum.
Solution 11.
a) To compute the sum of the three secret numbers, we can add up all the shares sent between
the parties:
A’s share sent to B(5) + B’s share sent to C(3) + C’s share sent to A(7)=5+3+7=15
Therefore, the sum of the three secret numbers is 15.
b) One potential security risk is collusion between two parties. If two parties collude and share
their secret shares, they can deduce the third secret share and thus compromise the secrecy of
the computed sum. In this case, if Aand Ccollude, they can add their secret shares to obtain B’s
secret share without Bknowing. This would reveal B’s secret and compromise the security of the
protocol.
10.1 12. DIFFICULTY IN ACHIEVING FORWARD SECRECY IN COMMUNICATION
PROTOCOLS
Problem 12. In a communication protocol, Alice and Bob agreed to use the Diffie-Hellman key
exchange algorithm to establish a shared secret key. Alice’s public key is g= 5 and p= 23. Bob’s
public key is g= 7 and p= 23. Given that the secret key (afor Alice and bfor Bob) is 6and 12
respectively, calculate the shared secret key.
Solution 12.
a) Alice calculates (gbmod p)amod pto obtain the shared secret key:
Alice: (76mod 23)12 mod 23
Calculating the values:
(279936 mod 23)12 mod 23
1412 mod 23
1,116,668,081,822,284 mod 23
21
Therefore, the shared secret key for Alice is 21.
b) Bob calculates (gamod p)bmod pto obtain the shared secret key:
Bob: (512 mod 23)6mod 23
Calculating the values:
(244140625 mod 23)6mod 23
186mod 23
34,992,033,553 mod 23
15
Therefore, the shared secret key for Bob is 15.
c) Since both Alice and Bob have calculated their respective shared secret keys, they can now
communicate securely using the Diffie-Hellman key exchange algorithm with a shared key of 15.
I. Problems on Cryptographic Algorithms and Protocols
11 13. CHALLENGES IN IMPLEMENTING HOMOMORPHIC ENCRYPTION
Problem 13. Consider a homomorphic encryption scheme where plaintexts are encoded as
integers mod 26. The encryption function takes a plaintext mand two random numbers r1and
r2to generate the ciphertext: c=m+r1mod 26 + r2mod 26. Suppose we want to perform a
homomorphic multiplication operation on two ciphertexts c1and c2, where c1= 10 and c2= 17.
Calculate the result of the homomorphic multiplication operation.
Solution 13. To perform homomorphic multiplication, we can simply multiply the ciphertexts:
cmul =c1×c2mod 26. Given c1= 10 and c2= 17, we have:
cmul = 10 ×17 mod 26 = 170 mod 26 = 12
Therefore, the result of the homomorphic multiplication operation on ciphertexts c1= 10 and
c2= 17 is cmul = 12.
This concludes the solution to the problem.
12 Cryptographic Algorithms and Protocols
Problem 1. Consider a simple substitution cipher where each letter of the alphabet is replaced
by a different letter. If we have encrypted the message "HELLO" using a substitution cipher and the
encryption key is as follows: {H→Q, E →B, L →X, O →M}, what is the encrypted message?
Problem 2. Alice and Bob want to establish a shared secret key using the Diffie-Hellman key
exchange protocol. If the prime number p= 23 and the primitive root α= 5, Alice chooses her
private key as a= 6 and Bob chooses his private key as b= 15, what is the shared secret key that
they will both compute?
Problem 3. In RSA encryption, if the public key is (n= 77, e = 7) and the message to be
encrypted is m= 13, what is the ciphertext produced using the RSA algorithm?
Solution 1. a) The encrypted message for "HELLO" using the substitution cipher key given
would be "QBXXM".
b) Alice computes her public key as A=αamod p= 56mod 23 = 8. Bob computes his
public key as B=αbmod p= 515 mod 23 = 19. The shared secret key is K=Bamod p= 196
mod 23 = 2.
c) To encrypt the message using RSA encryption, compute c=memod n= 137mod 77 =
16. Therefore, the ciphertext produced is 16.
13 Cryptographic Algorithms and Protocols
Problem 1. Consider a secure communication protocol that uses Diffie-Hellman key exchange
to establish a shared secret key between Alice and Bob. If the prime modulus p= 23 and the base
g= 5, determine the shared secret key when Alice chooses a private key a= 6 and Bob chooses
a private key b= 15.
Solution 1. The shared secret key can be calculated by both Alice and Bob using the following
steps:
a) Alice calculates A=gamod p:
A= 56mod 23 = 25 mod 23 = 2
b) Bob calculates B=gbmod p:
B= 515 mod 23 = 30,517,578,125 mod 23 = 19
c) Alice and Bob share their calculated values Aand B, respectively.
d) Alice calculates the shared secret key: K=Bamod p:
K= 196mod 23 = 47,045,881 mod 23 = 2
e) Bob calculates the shared secret key: K=Abmod p:
K= 215 mod 23 = 32,768 mod 23 = 2
Thus, the shared secret key for both Alice and Bob is 2.
Problem 2. In the RSA encryption algorithm, suppose Alice chooses two prime numbers p= 11
and q= 17 for her public and private keys. She also chooses the public encryption exponent e= 7.
Determine the private decryption exponent d.
Solution 2. To find the private decryption exponent d, we must first calculate the following: -
n=p×q= 11 ×17 = 187 -φ(n)=(p−1) ×(q−1) = 10 ×16 = 160 - Then we solve the equation
e×d≡1 (mod φ(n)) for d:
7d≡1 (mod 160)
Solving this congruence equation, we find d= 23.
I’m happy to help with that. Here is a numerical problem on Cryptographic Algorithms and
Protocols for you:
14 16. PROBLEMS WITH END-TO-END ENCRYPTION SOLUTIONS
Problem 16. Consider a scenario where Alice wants to securely communicate with Bob using end-
to-end encryption. They decide to use the RSA cryptosystem for encryption and decryption. Alice’s
public key is (eA, NA) = (5,143), and her private key is (dA, NA) = (29,143). Bob generates his
own keys where his public key is (eB, NB) = (3,187), and his private key is (dB, NB) = (107,187).
a) If Alice wants to send a message M = 25 to Bob, what is the ciphertext that will be sent over
the network?
b) If Bob receives the ciphertext C = 97 from Alice, what is the original message M that Alice
intended to send him?
Solution 16.
a) To encrypt the message M = 25 using Alice’s public key, we use the encryption function:
C=MeAmod NA
C= 255mod 143
C= 3125 mod 143
C= 49
Therefore, the ciphertext that will be sent over the network is 49.
b) To decrypt the ciphertext C = 97 using Bob’s private key, we use the decryption function:
M=CdBmod NB
M= 97107 mod 187
M= 136904183893900215547781596700000000000000000000000000000000000000000000000000000000000000000 < /br > mod 187
M= 25
Therefore, the original message that Alice intended to send to Bob is 25.
15 17. CHALLENGES IN ACHIEVING SECURE AUTHENTICATION IN DISTRIBUTED SYS-
TEMS
Problem 17. Consider a distributed system where three entities need to authenticate each other
using a challenge-response protocol based on a shared secret key. Entity Agenerates a random
challenge cA= 347, Entity Bgenerates a random challenge cB= 512, and Entity Cgenerates a
random challenge cC= 635. The shared secret key between all entities is K= 123.
a) Entity Asends cAto Entity B, who responds with the result of cA⊕K. Calculate the response
sent by Entity Bto Entity A.
b) Entity Bsends cBto Entity C, who responds with the result of cB⊕K. Calculate the response
sent by Entity Cto Entity B.
c) Entity Csends cCto Entity A, who responds with the result of cC⊕K. Calculate the response
sent by Entity Ato Entity C.
Solution 17.
a) Entity Bcalculates the response as cA⊕K:
cA⊕K= 347 ⊕123 = 224
Therefore, Entity Bsends the response 224 to Entity A.
b) Entity Ccalculates the response as cB⊕K:
cB⊕K= 512 ⊕123 = 635
Therefore, Entity Csends the response 635 to Entity B.
c) Entity Acalculates the response as cC⊕K:
cC⊕K= 635 ⊕123 = 756
Therefore, Entity Asends the response 756 to Entity C.
16 Cryptographic Algorithms and Protocols
Problem: Alice wants to securely send a message to Bob using symmetric encryption. She
chooses the block cipher AES with a key size of 128 bits. The message she wants to send is 1280
bits long.
a) How many blocks will the message be divided into for encryption using AES?
b) If Alice and Bob are using the Electronic Code Book (ECB) mode, explain what kind of
vulnerability may arise in this scenario.
Solution:
a) The AES block size is 128 bits (16 bytes), so the 1280-bit message will need to be divided
into blocks of size 128 bits each.
Number of blocks = Message size / Block size = 1280 bits / 128 bits = 10 blocks
Therefore, the message will be divided into 10 blocks for encryption using AES.
b) In the ECB mode, each block of plaintext is encrypted separately with the same key. This
means that identical plaintext blocks will result in identical ciphertext blocks. This vulnerability can
be exploited by an attacker to detect patterns in the encrypted data, potentially revealing information
or relationships within the message. Additionally, ECB does not provide semantic security, so it
may leak information even if the plaintext is encrypted.
In the given scenario, if Alice sends any message that contains repeated blocks of plaintext
(e.g., patterns, images, or repeated phrases), an attacker can identify these repetitions and poten-
tially infer information about the message’s content.
I am unable to provide numerical problem questions and solutions for Cryptographic Algorithms
and Protocols at the moment. Would you like me to assist you with theoretical concepts or any other
form of assistance related to this topic?
I can certainly provide a problem and solution for you!
17 Cryptographic Algorithms and Protocols
Problem:
Consider the following scenario in a public-key encryption system using RSA:
Alice wants to send a confidential message to Bob. Bob has a public encryption key (e, n) =
(17,323) and a private key (d, n) = (275,323). Alice encrypts her message as follows: she repre-
sents the message as a number where each letter is assigned a value (A=1, B=2, ..., Z=26), and
then raises this number to the power of the public key (e)modulo nto obtain the ciphertext.
Alice’s message is "HELLO". The numerical representation of this message is [8, 5, 12, 12,
15]. Calculate the ciphertext that Alice will send to Bob.
Solution:
To find the ciphertext for the message "HELLO", we will encrypt each letter separately and
combine the results.
Let’s encode each letter:
H: 8 E: 5 L: 12 L: 12 O: 15
For letter "H": 817 ≡106 (mod 323)
For letter "E": 517 ≡9 (mod 323)
For letter "L": 1217 ≡144 (mod 323)
For the second "L": 1217 ≡144 (mod 323)
For letter "O": 1517 ≡21 (mod 323)
Now, combine these ciphertext values: 1069194144214421
Therefore, the ciphertext that Alice will send to Bob for the message "HELLO" is 10691941442144.
3 3. VULNERABILITIES IN ASYMMETRIC ENCRYPTION SCHEMES
Problem 3. Consider the RSA encryption scheme with public key (e, N) = (7,187). An attacker
intercepts a message m= 65 encrypted using this public key.
a) Compute the private key d.
b) Determine the decrypted message.
Solution 3.
a) To compute the private key d, we need to find the value such that ed ≡1 (mod φ(N)), where
φ(N)is Euler’s totient function.
Given that N= 187, we first need to calculate φ(N):
φ(N)=(p−1)(q−1) = 10 ×18 = 180.
Next, we solve for d:
7d≡1 (mod 180).
Solving this congruence, we get d= 103.
b) To decrypt the message, we calculate cd(mod N), where cis the intercepted ciphertext.
m= 65103 (mod 187).
Using fast modular exponentiation, we can simplify this calculation:
652≡52 (mod 187),
654≡522≡64 (mod 187),
658≡642≡141 (mod 187),
6516 ≡1412≡145 (mod 187),
6532 ≡1452≡79 (mod 187),
6564 ≡792≡77 (mod 187).
Therefore,
65103 ≡65 ×6532 ×6516 ×652×651
≡65 ×79 ×145 ×52
≡64 (mod 187).
Hence, the decrypted message is m= 64.
4 4. CRYPTANALYSIS OF SYMMETRIC KEY ALGORITHMS
Problem 4. Consider a block cipher with a block size of 64 bits and a key size of 128 bits. An
attacker performs a known-plaintext attack where they obtain 10 plaintext-ciphertext pairs. Each
pair has a plaintext of 64 bits and a corresponding ciphertext of 64 bits. The attacker wants to
determine the key using this information.
a) What is the maximum number of key candidates that the attacker needs to try to recover the
key using exhaustive search?
b) If the attacker has 2 plaintext-ciphertext pairs chosen by themselves (not obtained from
known plaintext) and wants to use a chosen-plaintext attack, how many queries do they need to
make to uniquely determine the key?
Solution 4.
a) Since the key size is 128 bits, the total number of possible keys is 2128. With the given 10
plaintext-ciphertext pairs, the attacker needs to try each key candidate against all pairs. Therefore,
the maximum number of key candidates to try is 2128 = 340,282,366,920,938,463,463,374,607,431,768,211,456.
b) In a chosen-plaintext attack, the attacker can choose their plaintexts. With 2 plaintext-
ciphertext pairs, each pair contributes 64 bits of information about the key (block size). Since
the key size is 128 bits, the attacker needs a total of 128/64 = 2 pairs to uniquely determine the
key. Therefore, the attacker needs to make a total of 2 queries.
I. Problem:
Consider a side-channel attack on a symmetric encryption algorithm that leaks information
about the encryption key based on the power consumption during encryption. Suppose you have
the following data:
- Power consumption when encrypting the plaintext 0x45: 100 units - Power consumption when
encrypting the plaintext 0xAF: 150 units
Assume that the power consumption is directly related to the number of bit changes in the
encryption key during encryption.
a) Determine the Hamming distance (number of differing bits) between the encryption keys
used for encrypting the plaintexts 0x45 and 0xAF.
b) If the encryption key consists of 8 bits, find the average power consumption when encrypting
a plaintext using this encryption algorithm.
Solution:
a) To find the Hamming distance between the encryption keys used for the two plaintexts:
0x45 =0100 0101
0xAF =1010 1111
The Hamming distance is the number of bit positions in which the two binary strings differ:
Hamming distance = 3 (bits that differ are in positions 2, 5, and 7)
b) With an 8-bit key, each bit change contributes to the power consumption. From part a, we
calculated three differing bits in the encryption key. Thus, the average power consumption when
encrypting a plaintext is:
Average power consumption =Total power consumption
Number of bit changes =100+150
3=250
3≈83.33 units
Therefore, the average power consumption when encrypting a plaintext using this encryption
algorithm is approximately 83.33 units.
5 6. LACK OF PROTECTION AGAINST QUANTUM COMPUTING THREATS
Problem 6. Consider the Shor’s algorithm for integer factorization. Given N= 15, find the
prime factors of Nusing Shor’s algorithm.
Solution 6. a) According to Shor’s algorithm, we need to find the period of the function f(x) =
axmod N, where a= 2.
Let’s find the period:
•f(0) = 20mod 15 = 1
•f(1) = 21mod 15 = 2
•f(2) = 22mod 15 = 4
•f(3) = 23mod 15 = 8
•f(4) = 24mod 15 = 1
The smallest period is r= 4. We need to find a1= 2(r/2) mod 15. Since r= 4,a1= 22
mod 15 = 4.
Next, we solve the equation gcd(ar/2±1, N). Either gcd(4 + 1,15) or gcd(4 −1,15).
•gcd(5,15) = 5 is a factor of N.
Therefore, the prime factors of N= 15 are 5and 3.
Thus, the prime factors of Nare 3and 5.
b) In this part, we find the same prime factors of N= 15 using the general approach. We
factorize 15 to prime numbers: 15 = 3 ×5.
c) Compare the results obtained from Shor’s algorithm and the general approach.
The results from Shor’s algorithm (3and 5) and the general approach (3and 5) are the same,
confirming the accuracy of both methods.
6 7. RISK OF COLLUSION ATTACKS ON CRYPTOGRAPHIC SYSTEMS
Problem 7. Consider a cryptographic system that uses a key exchange protocol with npartic-
ipants. Each participant holds a secret key that is randomly generated. If kparticipants collude to
share their secret keys, what is the probability that the colluding participants can decrypt a message
encrypted using the system?
Assume that the system is secure as long as at least one participant’s key remains secret.
Solution 7.
To find the probability that the colluding participants can decrypt the message, we need to
calculate the probability that all kparticipants’ keys are shared.
Let’s denote the total number of participants as nand the number of colluding participants as
k. The probability that all kparticipants’ keys are shared can be calculated as follows:
a) Probability that the first participant’s key is shared: k
n
b) Probability that the second participant’s key is shared given that the first participant’s key is
shared: k−1
n−1
c) Probability that the k-th participant’s key is shared given that the previous k−1participants’
keys are shared: k−(k−1)
n−(k−1) =1
n−(k−1)
Therefore, the overall probability that all kparticipants’ keys are shared is:
P(All kkeys are shared) = k
n×k−1
n−1×. . . ×1
n−(k−1)
Substitute n= 10 and k= 3 into the formula:
P(All 3keys are shared) = 3
10 ×2
9×1
8=1
120
Therefore, the probability that the colluding participants can decrypt the message is 1
120 .
7 8. INSECURE RANDOM NUMBER GENERATION IN CRYPTOGRAPHIC ALGORITHMS
Problem 8. Consider a scenario where a cryptographic algorithm requires generating random
numbers for secure key generation. However, the random number generator used is insecure and
produces predictable outputs.
Assume the insecure random number generator outputs a sequence of numbers as follows: 4,
8, 12, 16, 20, 24, ...
a) Calculate the next three numbers that will be generated by this insecure random number
generator.
b) Explain why using such an insecure random number generator for cryptographic purposes
is problematic.
Solution 8.
a) The pattern observed in the sequence of numbers generated by the insecure random number
generator is incrementing by 4. Therefore, the next three numbers that will be generated are: - 28
- 32 - 36
b) Using an insecure random number generator for cryptographic purposes is problematic be-
cause it introduces predictability in generating cryptographic keys or other sensitive parameters.
If an attacker can predict the numbers being used to generate cryptographic keys, they may be
able to break the encryption scheme and compromise the security of the system. Randomness is
a crucial element in cryptographic protocols to ensure secure communication and protect sensitive
information.
8 9. WEAKNESSES IN HASH FUNCTIONS
Problem 9. Consider a hash function H(x)=(ax +b) mod 11, where a= 3 and b= 5.
a) Calculate H(7).
b) Find an input xsuch that H(x)=6.
c) Determine whether the given hash function is collision-resistant.
Solution 9.
a) To find H(7), substitute x= 7 into the hash function:
H(7) = (3 ·7 + 5) mod 11 = 26 mod 11 = 4
Therefore, H(7) = 4.
b) To find an input xsuch that H(x)=6, set H(x)=6and solve for x:
(3x+ 5) mod 11 = 6
3x+ 5 = 6 ·11 + k, where 0≤k < 11
3x+ 5 = 66 + k
3x= 61 + k
Since kcan take values from 0 to 10, we check for ksuch that (61 + k)is divisible by 3:
k= 1
3x= 62
x=62
3= 202
3
Therefore, an input xsuch that H(x)=6is not an integer.
c) The given hash function is not collision-resistant because multiple inputs can map to the
same output. For example, H(0) = 5 and H(11) = 5, showing a collision.
9 Cryptographic Algorithms and Protocols
Problem 1. Consider a digital signature scheme that uses the RSA algorithm with a modulus
N= 187 and public exponent e= 13. Alice signs a message by raising it to the power of d= 37
(mod 187). If the original message is m= 45, what is the signature that Alice sends?
Solution 1. Given that N= 187,e= 13,d= 37, and m= 45, we can calculate the signature
as follows:
1. Calculate the public key component:
public key = (N, e) = (187,13)
2. Calculate the private key component: Firstly, we need to find pand qsuch that N=p·q= 187.
Through factorization, we find that p= 11 and q= 17. Next, calculate ϕ(N) = (p−1)(q−1) =
10 ·16 = 160. Then, calculate the private key d=e−1(mod ϕ(N)).
d= 13−1(mod 160) = 37
3. Calculate the signature: The signature is calculated as:
signature =md(mod N) = 4537 (mod 187)
signature = 148
Therefore, Alice will send the signature 148 for the message m= 45.
10 11. ISSUES WITH SECURE MULTIPARTY COMPUTATION PROTOCOLS
Problem 11. Consider a secure multiparty computation protocol involving three parties A,B,
and C. Each party has a secret number that they want to compute the sum of without revealing
their individual values. The protocol involves additive secret sharing where each party splits their
secret into two shares and sends one share to each of the other parties. The sum of the three
secret numbers should be computed by combining the shares in a secure manner.
Suppose A’s secret share sent to Bis 5, B’s secret share sent to Cis 3, and C’s secret share
sent to Ais 7.
a) Determine the sum of the three secret numbers without revealing the individual secrets.
b) Discuss any potential security risks or attacks that could compromise the secrecy of the
computed sum.
Solution 11.
a) To compute the sum of the three secret numbers, we can add up all the shares sent between
the parties:
A’s share sent to B(5) + B’s share sent to C(3) + C’s share sent to A(7)=5+3+7=15
Therefore, the sum of the three secret numbers is 15.
b) One potential security risk is collusion between two parties. If two parties collude and share
their secret shares, they can deduce the third secret share and thus compromise the secrecy of
the computed sum. In this case, if Aand Ccollude, they can add their secret shares to obtain B’s
secret share without Bknowing. This would reveal B’s secret and compromise the security of the
protocol.
10.1 12. DIFFICULTY IN ACHIEVING FORWARD SECRECY IN COMMUNICATION
PROTOCOLS
Problem 12. In a communication protocol, Alice and Bob agreed to use the Diffie-Hellman key
exchange algorithm to establish a shared secret key. Alice’s public key is g= 5 and p= 23. Bob’s
public key is g= 7 and p= 23. Given that the secret key (afor Alice and bfor Bob) is 6and 12
respectively, calculate the shared secret key.
Solution 12.
a) Alice calculates (gbmod p)amod pto obtain the shared secret key:
Alice: (76mod 23)12 mod 23
Calculating the values:
(279936 mod 23)12 mod 23
1412 mod 23
1,116,668,081,822,284 mod 23
21
Therefore, the shared secret key for Alice is 21.
b) Bob calculates (gamod p)bmod pto obtain the shared secret key:
Bob: (512 mod 23)6mod 23
Calculating the values:
(244140625 mod 23)6mod 23
186mod 23
34,992,033,553 mod 23
15
Therefore, the shared secret key for Bob is 15.
c) Since both Alice and Bob have calculated their respective shared secret keys, they can now
communicate securely using the Diffie-Hellman key exchange algorithm with a shared key of 15.
I. Problems on Cryptographic Algorithms and Protocols
11 13. CHALLENGES IN IMPLEMENTING HOMOMORPHIC ENCRYPTION
Problem 13. Consider a homomorphic encryption scheme where plaintexts are encoded as
integers mod 26. The encryption function takes a plaintext mand two random numbers r1and
r2to generate the ciphertext: c=m+r1mod 26 + r2mod 26. Suppose we want to perform a
homomorphic multiplication operation on two ciphertexts c1and c2, where c1= 10 and c2= 17.
Calculate the result of the homomorphic multiplication operation.
Solution 13. To perform homomorphic multiplication, we can simply multiply the ciphertexts:
cmul =c1×c2mod 26. Given c1= 10 and c2= 17, we have:
cmul = 10 ×17 mod 26 = 170 mod 26 = 12
Therefore, the result of the homomorphic multiplication operation on ciphertexts c1= 10 and
c2= 17 is cmul = 12.
This concludes the solution to the problem.
12 Cryptographic Algorithms and Protocols
Problem 1. Consider a simple substitution cipher where each letter of the alphabet is replaced
by a different letter. If we have encrypted the message "HELLO" using a substitution cipher and the
encryption key is as follows: {H→Q, E →B, L →X, O →M}, what is the encrypted message?
Problem 2. Alice and Bob want to establish a shared secret key using the Diffie-Hellman key
exchange protocol. If the prime number p= 23 and the primitive root α= 5, Alice chooses her
private key as a= 6 and Bob chooses his private key as b= 15, what is the shared secret key that
they will both compute?
Problem 3. In RSA encryption, if the public key is (n= 77, e = 7) and the message to be
encrypted is m= 13, what is the ciphertext produced using the RSA algorithm?
Solution 1. a) The encrypted message for "HELLO" using the substitution cipher key given
would be "QBXXM".
b) Alice computes her public key as A=αamod p= 56mod 23 = 8. Bob computes his
public key as B=αbmod p= 515 mod 23 = 19. The shared secret key is K=Bamod p= 196
mod 23 = 2.
c) To encrypt the message using RSA encryption, compute c=memod n= 137mod 77 =
16. Therefore, the ciphertext produced is 16.
13 Cryptographic Algorithms and Protocols
Problem 1. Consider a secure communication protocol that uses Diffie-Hellman key exchange
to establish a shared secret key between Alice and Bob. If the prime modulus p= 23 and the base
g= 5, determine the shared secret key when Alice chooses a private key a= 6 and Bob chooses
a private key b= 15.
Solution 1. The shared secret key can be calculated by both Alice and Bob using the following
steps:
a) Alice calculates A=gamod p:
A= 56mod 23 = 25 mod 23 = 2
b) Bob calculates B=gbmod p:
B= 515 mod 23 = 30,517,578,125 mod 23 = 19
c) Alice and Bob share their calculated values Aand B, respectively.
d) Alice calculates the shared secret key: K=Bamod p:
K= 196mod 23 = 47,045,881 mod 23 = 2
e) Bob calculates the shared secret key: K=Abmod p:
K= 215 mod 23 = 32,768 mod 23 = 2
Thus, the shared secret key for both Alice and Bob is 2.
Problem 2. In the RSA encryption algorithm, suppose Alice chooses two prime numbers p= 11
and q= 17 for her public and private keys. She also chooses the public encryption exponent e= 7.
Determine the private decryption exponent d.
Solution 2. To find the private decryption exponent d, we must first calculate the following: -
n=p×q= 11 ×17 = 187 -φ(n)=(p−1) ×(q−1) = 10 ×16 = 160 - Then we solve the equation
e×d≡1 (mod φ(n)) for d:
7d≡1 (mod 160)
Solving this congruence equation, we find d= 23.
I’m happy to help with that. Here is a numerical problem on Cryptographic Algorithms and
Protocols for you:
14 16. PROBLEMS WITH END-TO-END ENCRYPTION SOLUTIONS
Problem 16. Consider a scenario where Alice wants to securely communicate with Bob using end-
to-end encryption. They decide to use the RSA cryptosystem for encryption and decryption. Alice’s
public key is (eA, NA) = (5,143), and her private key is (dA, NA) = (29,143). Bob generates his
own keys where his public key is (eB, NB) = (3,187), and his private key is (dB, NB) = (107,187).
a) If Alice wants to send a message M = 25 to Bob, what is the ciphertext that will be sent over
the network?
b) If Bob receives the ciphertext C = 97 from Alice, what is the original message M that Alice
intended to send him?
Solution 16.
a) To encrypt the message M = 25 using Alice’s public key, we use the encryption function:
C=MeAmod NA
C= 255mod 143
C= 3125 mod 143
C= 49
Therefore, the ciphertext that will be sent over the network is 49.
b) To decrypt the ciphertext C = 97 using Bob’s private key, we use the decryption function:
M=CdBmod NB
M= 97107 mod 187
M= 136904183893900215547781596700000000000000000000000000000000000000000000000000000000000000000 < /br > mod 187
M= 25
Therefore, the original message that Alice intended to send to Bob is 25.
15 17. CHALLENGES IN ACHIEVING SECURE AUTHENTICATION IN DISTRIBUTED SYS-
TEMS
Problem 17. Consider a distributed system where three entities need to authenticate each other
using a challenge-response protocol based on a shared secret key. Entity Agenerates a random
challenge cA= 347, Entity Bgenerates a random challenge cB= 512, and Entity Cgenerates a
random challenge cC= 635. The shared secret key between all entities is K= 123.
a) Entity Asends cAto Entity B, who responds with the result of cA⊕K. Calculate the response
sent by Entity Bto Entity A.
b) Entity Bsends cBto Entity C, who responds with the result of cB⊕K. Calculate the response
sent by Entity Cto Entity B.
c) Entity Csends cCto Entity A, who responds with the result of cC⊕K. Calculate the response
sent by Entity Ato Entity C.
Solution 17.
a) Entity Bcalculates the response as cA⊕K:
cA⊕K= 347 ⊕123 = 224
Therefore, Entity Bsends the response 224 to Entity A.
b) Entity Ccalculates the response as cB⊕K:
cB⊕K= 512 ⊕123 = 635
Therefore, Entity Csends the response 635 to Entity B.
c) Entity Acalculates the response as cC⊕K:
cC⊕K= 635 ⊕123 = 756
Therefore, Entity Asends the response 756 to Entity C.
16 Cryptographic Algorithms and Protocols
Problem: Alice wants to securely send a message to Bob using symmetric encryption. She
chooses the block cipher AES with a key size of 128 bits. The message she wants to send is 1280
bits long.
a) How many blocks will the message be divided into for encryption using AES?
b) If Alice and Bob are using the Electronic Code Book (ECB) mode, explain what kind of
vulnerability may arise in this scenario.
Solution:
a) The AES block size is 128 bits (16 bytes), so the 1280-bit message will need to be divided
into blocks of size 128 bits each.
Number of blocks = Message size / Block size = 1280 bits / 128 bits = 10 blocks
Therefore, the message will be divided into 10 blocks for encryption using AES.
b) In the ECB mode, each block of plaintext is encrypted separately with the same key. This
means that identical plaintext blocks will result in identical ciphertext blocks. This vulnerability can
be exploited by an attacker to detect patterns in the encrypted data, potentially revealing information
or relationships within the message. Additionally, ECB does not provide semantic security, so it
may leak information even if the plaintext is encrypted.
In the given scenario, if Alice sends any message that contains repeated blocks of plaintext
(e.g., patterns, images, or repeated phrases), an attacker can identify these repetitions and poten-
tially infer information about the message’s content.
I am unable to provide numerical problem questions and solutions for Cryptographic Algorithms
and Protocols at the moment. Would you like me to assist you with theoretical concepts or any other
form of assistance related to this topic?
I can certainly provide a problem and solution for you!
17 Cryptographic Algorithms and Protocols
Problem:
Consider the following scenario in a public-key encryption system using RSA:
Alice wants to send a confidential message to Bob. Bob has a public encryption key (e, n) =
(17,323) and a private key (d, n) = (275,323). Alice encrypts her message as follows: she repre-
sents the message as a number where each letter is assigned a value (A=1, B=2, ..., Z=26), and
then raises this number to the power of the public key (e)modulo nto obtain the ciphertext.
Alice’s message is "HELLO". The numerical representation of this message is [8, 5, 12, 12,
15]. Calculate the ciphertext that Alice will send to Bob.
Solution:
To find the ciphertext for the message "HELLO", we will encrypt each letter separately and
combine the results.
Let’s encode each letter:
H: 8 E: 5 L: 12 L: 12 O: 15
For letter "H": 817 ≡106 (mod 323)
For letter "E": 517 ≡9 (mod 323)
For letter "L": 1217 ≡144 (mod 323)
For the second "L": 1217 ≡144 (mod 323)
For letter "O": 1517 ≡21 (mod 323)
Now, combine these ciphertext values: 1069194144214421
Therefore, the ciphertext that Alice will send to Bob for the message "HELLO" is 10691941442144.
3 3. VULNERABILITIES IN ASYMMETRIC ENCRYPTION SCHEMES
Problem 3. Consider the RSA encryption scheme with public key (e, N) = (7,187). An attacker
intercepts a message m= 65 encrypted using this public key.
a) Compute the private key d.
b) Determine the decrypted message.
Solution 3.
a) To compute the private key d, we need to find the value such that ed ≡1 (mod φ(N)), where
φ(N)is Euler’s totient function.
Given that N= 187, we first need to calculate φ(N):
φ(N)=(p−1)(q−1) = 10 ×18 = 180.
Next, we solve for d:
7d≡1 (mod 180).
Solving this congruence, we get d= 103.
b) To decrypt the message, we calculate cd(mod N), where cis the intercepted ciphertext.
m= 65103 (mod 187).
Using fast modular exponentiation, we can simplify this calculation:
652≡52 (mod 187),
654≡522≡64 (mod 187),
658≡642≡141 (mod 187),
6516 ≡1412≡145 (mod 187),
6532 ≡1452≡79 (mod 187),
6564 ≡792≡77 (mod 187).
Therefore,
65103 ≡65 ×6532 ×6516 ×652×651
≡65 ×79 ×145 ×52
≡64 (mod 187).
Hence, the decrypted message is m= 64.
4 4. CRYPTANALYSIS OF SYMMETRIC KEY ALGORITHMS
Problem 4. Consider a block cipher with a block size of 64 bits and a key size of 128 bits. An
attacker performs a known-plaintext attack where they obtain 10 plaintext-ciphertext pairs. Each
pair has a plaintext of 64 bits and a corresponding ciphertext of 64 bits. The attacker wants to
determine the key using this information.
a) What is the maximum number of key candidates that the attacker needs to try to recover the
key using exhaustive search?
b) If the attacker has 2 plaintext-ciphertext pairs chosen by themselves (not obtained from
known plaintext) and wants to use a chosen-plaintext attack, how many queries do they need to
make to uniquely determine the key?
Solution 4.
a) Since the key size is 128 bits, the total number of possible keys is 2128. With the given 10
plaintext-ciphertext pairs, the attacker needs to try each key candidate against all pairs. Therefore,
the maximum number of key candidates to try is 2128 = 340,282,366,920,938,463,463,374,607,431,768,211,456.
b) In a chosen-plaintext attack, the attacker can choose their plaintexts. With 2 plaintext-
ciphertext pairs, each pair contributes 64 bits of information about the key (block size). Since
the key size is 128 bits, the attacker needs a total of 128/64 = 2 pairs to uniquely determine the
key. Therefore, the attacker needs to make a total of 2 queries.
I. Problem:
Consider a side-channel attack on a symmetric encryption algorithm that leaks information
about the encryption key based on the power consumption during encryption. Suppose you have
the following data:
- Power consumption when encrypting the plaintext 0x45: 100 units - Power consumption when
encrypting the plaintext 0xAF: 150 units
Assume that the power consumption is directly related to the number of bit changes in the
encryption key during encryption.
a) Determine the Hamming distance (number of differing bits) between the encryption keys
used for encrypting the plaintexts 0x45 and 0xAF.
b) If the encryption key consists of 8 bits, find the average power consumption when encrypting
a plaintext using this encryption algorithm.
Solution:
a) To find the Hamming distance between the encryption keys used for the two plaintexts:
0x45 =0100 0101
0xAF =1010 1111
The Hamming distance is the number of bit positions in which the two binary strings differ:
Hamming distance = 3 (bits that differ are in positions 2, 5, and 7)
b) With an 8-bit key, each bit change contributes to the power consumption. From part a, we
calculated three differing bits in the encryption key. Thus, the average power consumption when
encrypting a plaintext is:
Average power consumption =Total power consumption
Number of bit changes =100+150
3=250
3≈83.33 units
Therefore, the average power consumption when encrypting a plaintext using this encryption
algorithm is approximately 83.33 units.
5 6. LACK OF PROTECTION AGAINST QUANTUM COMPUTING THREATS
Problem 6. Consider the Shor’s algorithm for integer factorization. Given N= 15, find the
prime factors of Nusing Shor’s algorithm.
Solution 6. a) According to Shor’s algorithm, we need to find the period of the function f(x) =
axmod N, where a= 2.
Let’s find the period:
•f(0) = 20mod 15 = 1
•f(1) = 21mod 15 = 2
•f(2) = 22mod 15 = 4
•f(3) = 23mod 15 = 8
•f(4) = 24mod 15 = 1
The smallest period is r= 4. We need to find a1= 2(r/2) mod 15. Since r= 4,a1= 22
mod 15 = 4.
Next, we solve the equation gcd(ar/2±1, N). Either gcd(4 + 1,15) or gcd(4 −1,15).
•gcd(5,15) = 5 is a factor of N.
Therefore, the prime factors of N= 15 are 5and 3.
Thus, the prime factors of Nare 3and 5.
b) In this part, we find the same prime factors of N= 15 using the general approach. We
factorize 15 to prime numbers: 15 = 3 ×5.
c) Compare the results obtained from Shor’s algorithm and the general approach.
The results from Shor’s algorithm (3and 5) and the general approach (3and 5) are the same,
confirming the accuracy of both methods.
6 7. RISK OF COLLUSION ATTACKS ON CRYPTOGRAPHIC SYSTEMS
Problem 7. Consider a cryptographic system that uses a key exchange protocol with npartic-
ipants. Each participant holds a secret key that is randomly generated. If kparticipants collude to
share their secret keys, what is the probability that the colluding participants can decrypt a message
encrypted using the system?
Assume that the system is secure as long as at least one participant’s key remains secret.
Solution 7.
To find the probability that the colluding participants can decrypt the message, we need to
calculate the probability that all kparticipants’ keys are shared.
Let’s denote the total number of participants as nand the number of colluding participants as
k. The probability that all kparticipants’ keys are shared can be calculated as follows:
a) Probability that the first participant’s key is shared: k
n
b) Probability that the second participant’s key is shared given that the first participant’s key is
shared: k−1
n−1
c) Probability that the k-th participant’s key is shared given that the previous k−1participants’
keys are shared: k−(k−1)
n−(k−1) =1
n−(k−1)
Therefore, the overall probability that all kparticipants’ keys are shared is:
P(All kkeys are shared) = k
n×k−1
n−1×. . . ×1
n−(k−1)
Substitute n= 10 and k= 3 into the formula:
P(All 3keys are shared) = 3
10 ×2
9×1
8=1
120
Therefore, the probability that the colluding participants can decrypt the message is 1
120 .
7 8. INSECURE RANDOM NUMBER GENERATION IN CRYPTOGRAPHIC ALGORITHMS
Problem 8. Consider a scenario where a cryptographic algorithm requires generating random
numbers for secure key generation. However, the random number generator used is insecure and
produces predictable outputs.
Assume the insecure random number generator outputs a sequence of numbers as follows: 4,
8, 12, 16, 20, 24, ...
a) Calculate the next three numbers that will be generated by this insecure random number
generator.
b) Explain why using such an insecure random number generator for cryptographic purposes
is problematic.
Solution 8.
a) The pattern observed in the sequence of numbers generated by the insecure random number
generator is incrementing by 4. Therefore, the next three numbers that will be generated are: - 28
- 32 - 36
b) Using an insecure random number generator for cryptographic purposes is problematic be-
cause it introduces predictability in generating cryptographic keys or other sensitive parameters.
If an attacker can predict the numbers being used to generate cryptographic keys, they may be
able to break the encryption scheme and compromise the security of the system. Randomness is
a crucial element in cryptographic protocols to ensure secure communication and protect sensitive
information.
8 9. WEAKNESSES IN HASH FUNCTIONS
Problem 9. Consider a hash function H(x)=(ax +b) mod 11, where a= 3 and b= 5.
a) Calculate H(7).
b) Find an input xsuch that H(x)=6.
c) Determine whether the given hash function is collision-resistant.
Solution 9.
a) To find H(7), substitute x= 7 into the hash function:
H(7) = (3 ·7 + 5) mod 11 = 26 mod 11 = 4
Therefore, H(7) = 4.
b) To find an input xsuch that H(x)=6, set H(x)=6and solve for x:
(3x+ 5) mod 11 = 6
3x+ 5 = 6 ·11 + k, where 0≤k < 11
3x+ 5 = 66 + k
3x= 61 + k
Since kcan take values from 0 to 10, we check for ksuch that (61 + k)is divisible by 3:
k= 1
3x= 62
x=62
3= 202
3
Therefore, an input xsuch that H(x)=6is not an integer.
c) The given hash function is not collision-resistant because multiple inputs can map to the
same output. For example, H(0) = 5 and H(11) = 5, showing a collision.
9 Cryptographic Algorithms and Protocols
Problem 1. Consider a digital signature scheme that uses the RSA algorithm with a modulus
N= 187 and public exponent e= 13. Alice signs a message by raising it to the power of d= 37
(mod 187). If the original message is m= 45, what is the signature that Alice sends?
Solution 1. Given that N= 187,e= 13,d= 37, and m= 45, we can calculate the signature
as follows:
1. Calculate the public key component:
public key = (N, e) = (187,13)
2. Calculate the private key component: Firstly, we need to find pand qsuch that N=p·q= 187.
Through factorization, we find that p= 11 and q= 17. Next, calculate ϕ(N) = (p−1)(q−1) =
10 ·16 = 160. Then, calculate the private key d=e−1(mod ϕ(N)).
d= 13−1(mod 160) = 37
3. Calculate the signature: The signature is calculated as:
signature =md(mod N) = 4537 (mod 187)
signature = 148
Therefore, Alice will send the signature 148 for the message m= 45.
10 11. ISSUES WITH SECURE MULTIPARTY COMPUTATION PROTOCOLS
Problem 11. Consider a secure multiparty computation protocol involving three parties A,B,
and C. Each party has a secret number that they want to compute the sum of without revealing
their individual values. The protocol involves additive secret sharing where each party splits their
secret into two shares and sends one share to each of the other parties. The sum of the three
secret numbers should be computed by combining the shares in a secure manner.
Suppose A’s secret share sent to Bis 5, B’s secret share sent to Cis 3, and C’s secret share
sent to Ais 7.
a) Determine the sum of the three secret numbers without revealing the individual secrets.
b) Discuss any potential security risks or attacks that could compromise the secrecy of the
computed sum.
Solution 11.
a) To compute the sum of the three secret numbers, we can add up all the shares sent between
the parties:
A’s share sent to B(5) + B’s share sent to C(3) + C’s share sent to A(7)=5+3+7=15
Therefore, the sum of the three secret numbers is 15.
b) One potential security risk is collusion between two parties. If two parties collude and share
their secret shares, they can deduce the third secret share and thus compromise the secrecy of
the computed sum. In this case, if Aand Ccollude, they can add their secret shares to obtain B’s
secret share without Bknowing. This would reveal B’s secret and compromise the security of the
protocol.
10.1 12. DIFFICULTY IN ACHIEVING FORWARD SECRECY IN COMMUNICATION
PROTOCOLS
Problem 12. In a communication protocol, Alice and Bob agreed to use the Diffie-Hellman key
exchange algorithm to establish a shared secret key. Alice’s public key is g= 5 and p= 23. Bob’s
public key is g= 7 and p= 23. Given that the secret key (afor Alice and bfor Bob) is 6and 12
respectively, calculate the shared secret key.
Solution 12.
a) Alice calculates (gbmod p)amod pto obtain the shared secret key:
Alice: (76mod 23)12 mod 23
Calculating the values:
(279936 mod 23)12 mod 23
1412 mod 23
1,116,668,081,822,284 mod 23
21
Therefore, the shared secret key for Alice is 21.
b) Bob calculates (gamod p)bmod pto obtain the shared secret key:
Bob: (512 mod 23)6mod 23
Calculating the values:
(244140625 mod 23)6mod 23
186mod 23
34,992,033,553 mod 23
15
Therefore, the shared secret key for Bob is 15.
c) Since both Alice and Bob have calculated their respective shared secret keys, they can now
communicate securely using the Diffie-Hellman key exchange algorithm with a shared key of 15.
I. Problems on Cryptographic Algorithms and Protocols
11 13. CHALLENGES IN IMPLEMENTING HOMOMORPHIC ENCRYPTION
Problem 13. Consider a homomorphic encryption scheme where plaintexts are encoded as
integers mod 26. The encryption function takes a plaintext mand two random numbers r1and
r2to generate the ciphertext: c=m+r1mod 26 + r2mod 26. Suppose we want to perform a
homomorphic multiplication operation on two ciphertexts c1and c2, where c1= 10 and c2= 17.
Calculate the result of the homomorphic multiplication operation.
Solution 13. To perform homomorphic multiplication, we can simply multiply the ciphertexts:
cmul =c1×c2mod 26. Given c1= 10 and c2= 17, we have:
cmul = 10 ×17 mod 26 = 170 mod 26 = 12
Therefore, the result of the homomorphic multiplication operation on ciphertexts c1= 10 and
c2= 17 is cmul = 12.
This concludes the solution to the problem.
12 Cryptographic Algorithms and Protocols
Problem 1. Consider a simple substitution cipher where each letter of the alphabet is replaced
by a different letter. If we have encrypted the message "HELLO" using a substitution cipher and the
encryption key is as follows: {H→Q, E →B, L →X, O →M}, what is the encrypted message?
Problem 2. Alice and Bob want to establish a shared secret key using the Diffie-Hellman key
exchange protocol. If the prime number p= 23 and the primitive root α= 5, Alice chooses her
private key as a= 6 and Bob chooses his private key as b= 15, what is the shared secret key that
they will both compute?
Problem 3. In RSA encryption, if the public key is (n= 77, e = 7) and the message to be
encrypted is m= 13, what is the ciphertext produced using the RSA algorithm?
Solution 1. a) The encrypted message for "HELLO" using the substitution cipher key given
would be "QBXXM".
b) Alice computes her public key as A=αamod p= 56mod 23 = 8. Bob computes his
public key as B=αbmod p= 515 mod 23 = 19. The shared secret key is K=Bamod p= 196
mod 23 = 2.
c) To encrypt the message using RSA encryption, compute c=memod n= 137mod 77 =
16. Therefore, the ciphertext produced is 16.
13 Cryptographic Algorithms and Protocols
Problem 1. Consider a secure communication protocol that uses Diffie-Hellman key exchange
to establish a shared secret key between Alice and Bob. If the prime modulus p= 23 and the base
g= 5, determine the shared secret key when Alice chooses a private key a= 6 and Bob chooses
a private key b= 15.
Solution 1. The shared secret key can be calculated by both Alice and Bob using the following
steps:
a) Alice calculates A=gamod p:
A= 56mod 23 = 25 mod 23 = 2
b) Bob calculates B=gbmod p:
B= 515 mod 23 = 30,517,578,125 mod 23 = 19
c) Alice and Bob share their calculated values Aand B, respectively.
d) Alice calculates the shared secret key: K=Bamod p:
K= 196mod 23 = 47,045,881 mod 23 = 2
e) Bob calculates the shared secret key: K=Abmod p:
K= 215 mod 23 = 32,768 mod 23 = 2
Thus, the shared secret key for both Alice and Bob is 2.
Problem 2. In the RSA encryption algorithm, suppose Alice chooses two prime numbers p= 11
and q= 17 for her public and private keys. She also chooses the public encryption exponent e= 7.
Determine the private decryption exponent d.
Solution 2. To find the private decryption exponent d, we must first calculate the following: -
n=p×q= 11 ×17 = 187 -φ(n)=(p−1) ×(q−1) = 10 ×16 = 160 - Then we solve the equation
e×d≡1 (mod φ(n)) for d:
7d≡1 (mod 160)
Solving this congruence equation, we find d= 23.
I’m happy to help with that. Here is a numerical problem on Cryptographic Algorithms and
Protocols for you:
14 16. PROBLEMS WITH END-TO-END ENCRYPTION SOLUTIONS
Problem 16. Consider a scenario where Alice wants to securely communicate with Bob using end-
to-end encryption. They decide to use the RSA cryptosystem for encryption and decryption. Alice’s
public key is (eA, NA) = (5,143), and her private key is (dA, NA) = (29,143). Bob generates his
own keys where his public key is (eB, NB) = (3,187), and his private key is (dB, NB) = (107,187).
a) If Alice wants to send a message M = 25 to Bob, what is the ciphertext that will be sent over
the network?
b) If Bob receives the ciphertext C = 97 from Alice, what is the original message M that Alice
intended to send him?
Solution 16.
a) To encrypt the message M = 25 using Alice’s public key, we use the encryption function:
C=MeAmod NA
C= 255mod 143
C= 3125 mod 143
C= 49
Therefore, the ciphertext that will be sent over the network is 49.
b) To decrypt the ciphertext C = 97 using Bob’s private key, we use the decryption function:
M=CdBmod NB
M= 97107 mod 187
M= 136904183893900215547781596700000000000000000000000000000000000000000000000000000000000000000 < /br > mod 187
M= 25
Therefore, the original message that Alice intended to send to Bob is 25.
15 17. CHALLENGES IN ACHIEVING SECURE AUTHENTICATION IN DISTRIBUTED SYS-
TEMS
Problem 17. Consider a distributed system where three entities need to authenticate each other
using a challenge-response protocol based on a shared secret key. Entity Agenerates a random
challenge cA= 347, Entity Bgenerates a random challenge cB= 512, and Entity Cgenerates a
random challenge cC= 635. The shared secret key between all entities is K= 123.
a) Entity Asends cAto Entity B, who responds with the result of cA⊕K. Calculate the response
sent by Entity Bto Entity A.
b) Entity Bsends cBto Entity C, who responds with the result of cB⊕K. Calculate the response
sent by Entity Cto Entity B.
c) Entity Csends cCto Entity A, who responds with the result of cC⊕K. Calculate the response
sent by Entity Ato Entity C.
Solution 17.
a) Entity Bcalculates the response as cA⊕K:
cA⊕K= 347 ⊕123 = 224
Therefore, Entity Bsends the response 224 to Entity A.
b) Entity Ccalculates the response as cB⊕K:
cB⊕K= 512 ⊕123 = 635
Therefore, Entity Csends the response 635 to Entity B.
c) Entity Acalculates the response as cC⊕K:
cC⊕K= 635 ⊕123 = 756
Therefore, Entity Asends the response 756 to Entity C.
16 Cryptographic Algorithms and Protocols
Problem: Alice wants to securely send a message to Bob using symmetric encryption. She
chooses the block cipher AES with a key size of 128 bits. The message she wants to send is 1280
bits long.
a) How many blocks will the message be divided into for encryption using AES?
b) If Alice and Bob are using the Electronic Code Book (ECB) mode, explain what kind of
vulnerability may arise in this scenario.
Solution:
a) The AES block size is 128 bits (16 bytes), so the 1280-bit message will need to be divided
into blocks of size 128 bits each.
Number of blocks = Message size / Block size = 1280 bits / 128 bits = 10 blocks
Therefore, the message will be divided into 10 blocks for encryption using AES.
b) In the ECB mode, each block of plaintext is encrypted separately with the same key. This
means that identical plaintext blocks will result in identical ciphertext blocks. This vulnerability can
be exploited by an attacker to detect patterns in the encrypted data, potentially revealing information
or relationships within the message. Additionally, ECB does not provide semantic security, so it
may leak information even if the plaintext is encrypted.
In the given scenario, if Alice sends any message that contains repeated blocks of plaintext
(e.g., patterns, images, or repeated phrases), an attacker can identify these repetitions and poten-
tially infer information about the message’s content.
I am unable to provide numerical problem questions and solutions for Cryptographic Algorithms
and Protocols at the moment. Would you like me to assist you with theoretical concepts or any other
form of assistance related to this topic?
I can certainly provide a problem and solution for you!
17 Cryptographic Algorithms and Protocols
Problem:
Consider the following scenario in a public-key encryption system using RSA:
Alice wants to send a confidential message to Bob. Bob has a public encryption key (e, n) =
(17,323) and a private key (d, n) = (275,323). Alice encrypts her message as follows: she repre-
sents the message as a number where each letter is assigned a value (A=1, B=2, ..., Z=26), and
then raises this number to the power of the public key (e)modulo nto obtain the ciphertext.
Alice’s message is "HELLO". The numerical representation of this message is [8, 5, 12, 12,
15]. Calculate the ciphertext that Alice will send to Bob.
Solution:
To find the ciphertext for the message "HELLO", we will encrypt each letter separately and
combine the results.
Let’s encode each letter:
H: 8 E: 5 L: 12 L: 12 O: 15
For letter "H": 817 ≡106 (mod 323)
For letter "E": 517 ≡9 (mod 323)
For letter "L": 1217 ≡144 (mod 323)
For the second "L": 1217 ≡144 (mod 323)
For letter "O": 1517 ≡21 (mod 323)
Now, combine these ciphertext values: 1069194144214421
Therefore, the ciphertext that Alice will send to Bob for the message "HELLO" is 10691941442144.
3 3. VULNERABILITIES IN ASYMMETRIC ENCRYPTION SCHEMES
Problem 3. Consider the RSA encryption scheme with public key (e, N) = (7,187). An attacker
intercepts a message m= 65 encrypted using this public key.
a) Compute the private key d.
b) Determine the decrypted message.
Solution 3.
a) To compute the private key d, we need to find the value such that ed ≡1 (mod φ(N)), where
φ(N)is Euler’s totient function.
Given that N= 187, we first need to calculate φ(N):
φ(N)=(p−1)(q−1) = 10 ×18 = 180.
Next, we solve for d:
7d≡1 (mod 180).
Solving this congruence, we get d= 103.
b) To decrypt the message, we calculate cd(mod N), where cis the intercepted ciphertext.
m= 65103 (mod 187).
Using fast modular exponentiation, we can simplify this calculation:
652≡52 (mod 187),
654≡522≡64 (mod 187),
658≡642≡141 (mod 187),
6516 ≡1412≡145 (mod 187),
6532 ≡1452≡79 (mod 187),
6564 ≡792≡77 (mod 187).
Therefore,
65103 ≡65 ×6532 ×6516 ×652×651
≡65 ×79 ×145 ×52
≡64 (mod 187).
Hence, the decrypted message is m= 64.
4 4. CRYPTANALYSIS OF SYMMETRIC KEY ALGORITHMS
Problem 4. Consider a block cipher with a block size of 64 bits and a key size of 128 bits. An
attacker performs a known-plaintext attack where they obtain 10 plaintext-ciphertext pairs. Each
pair has a plaintext of 64 bits and a corresponding ciphertext of 64 bits. The attacker wants to
determine the key using this information.
a) What is the maximum number of key candidates that the attacker needs to try to recover the
key using exhaustive search?
b) If the attacker has 2 plaintext-ciphertext pairs chosen by themselves (not obtained from
known plaintext) and wants to use a chosen-plaintext attack, how many queries do they need to
make to uniquely determine the key?
Solution 4.
a) Since the key size is 128 bits, the total number of possible keys is 2128. With the given 10
plaintext-ciphertext pairs, the attacker needs to try each key candidate against all pairs. Therefore,
the maximum number of key candidates to try is 2128 = 340,282,366,920,938,463,463,374,607,431,768,211,456.
b) In a chosen-plaintext attack, the attacker can choose their plaintexts. With 2 plaintext-
ciphertext pairs, each pair contributes 64 bits of information about the key (block size). Since
the key size is 128 bits, the attacker needs a total of 128/64 = 2 pairs to uniquely determine the
key. Therefore, the attacker needs to make a total of 2 queries.
I. Problem:
Consider a side-channel attack on a symmetric encryption algorithm that leaks information
about the encryption key based on the power consumption during encryption. Suppose you have
the following data:
- Power consumption when encrypting the plaintext 0x45: 100 units - Power consumption when
encrypting the plaintext 0xAF: 150 units
Assume that the power consumption is directly related to the number of bit changes in the
encryption key during encryption.
a) Determine the Hamming distance (number of differing bits) between the encryption keys
used for encrypting the plaintexts 0x45 and 0xAF.
b) If the encryption key consists of 8 bits, find the average power consumption when encrypting
a plaintext using this encryption algorithm.
Solution:
a) To find the Hamming distance between the encryption keys used for the two plaintexts:
0x45 =0100 0101
0xAF =1010 1111
The Hamming distance is the number of bit positions in which the two binary strings differ:
Hamming distance = 3 (bits that differ are in positions 2, 5, and 7)
b) With an 8-bit key, each bit change contributes to the power consumption. From part a, we
calculated three differing bits in the encryption key. Thus, the average power consumption when
encrypting a plaintext is:
Average power consumption =Total power consumption
Number of bit changes =100+150
3=250
3≈83.33 units
Therefore, the average power consumption when encrypting a plaintext using this encryption
algorithm is approximately 83.33 units.
5 6. LACK OF PROTECTION AGAINST QUANTUM COMPUTING THREATS
Problem 6. Consider the Shor’s algorithm for integer factorization. Given N= 15, find the
prime factors of Nusing Shor’s algorithm.
Solution 6. a) According to Shor’s algorithm, we need to find the period of the function f(x) =
axmod N, where a= 2.
Let’s find the period:
•f(0) = 20mod 15 = 1
•f(1) = 21mod 15 = 2
•f(2) = 22mod 15 = 4
•f(3) = 23mod 15 = 8
•f(4) = 24mod 15 = 1
The smallest period is r= 4. We need to find a1= 2(r/2) mod 15. Since r= 4,a1= 22
mod 15 = 4.
Next, we solve the equation gcd(ar/2±1, N). Either gcd(4 + 1,15) or gcd(4 −1,15).
•gcd(5,15) = 5 is a factor of N.
Therefore, the prime factors of N= 15 are 5and 3.
Thus, the prime factors of Nare 3and 5.
b) In this part, we find the same prime factors of N= 15 using the general approach. We
factorize 15 to prime numbers: 15 = 3 ×5.
c) Compare the results obtained from Shor’s algorithm and the general approach.
The results from Shor’s algorithm (3and 5) and the general approach (3and 5) are the same,
confirming the accuracy of both methods.
6 7. RISK OF COLLUSION ATTACKS ON CRYPTOGRAPHIC SYSTEMS
Problem 7. Consider a cryptographic system that uses a key exchange protocol with npartic-
ipants. Each participant holds a secret key that is randomly generated. If kparticipants collude to
share their secret keys, what is the probability that the colluding participants can decrypt a message
encrypted using the system?
Assume that the system is secure as long as at least one participant’s key remains secret.
Solution 7.
To find the probability that the colluding participants can decrypt the message, we need to
calculate the probability that all kparticipants’ keys are shared.
Let’s denote the total number of participants as nand the number of colluding participants as
k. The probability that all kparticipants’ keys are shared can be calculated as follows:
a) Probability that the first participant’s key is shared: k
n
b) Probability that the second participant’s key is shared given that the first participant’s key is
shared: k−1
n−1
c) Probability that the k-th participant’s key is shared given that the previous k−1participants’
keys are shared: k−(k−1)
n−(k−1) =1
n−(k−1)
Therefore, the overall probability that all kparticipants’ keys are shared is:
P(All kkeys are shared) = k
n×k−1
n−1×. . . ×1
n−(k−1)
Substitute n= 10 and k= 3 into the formula:
P(All 3keys are shared) = 3
10 ×2
9×1
8=1
120
Therefore, the probability that the colluding participants can decrypt the message is 1
120 .
7 8. INSECURE RANDOM NUMBER GENERATION IN CRYPTOGRAPHIC ALGORITHMS
Problem 8. Consider a scenario where a cryptographic algorithm requires generating random
numbers for secure key generation. However, the random number generator used is insecure and
produces predictable outputs.
Assume the insecure random number generator outputs a sequence of numbers as follows: 4,
8, 12, 16, 20, 24, ...
a) Calculate the next three numbers that will be generated by this insecure random number
generator.
b) Explain why using such an insecure random number generator for cryptographic purposes
is problematic.
Solution 8.
a) The pattern observed in the sequence of numbers generated by the insecure random number
generator is incrementing by 4. Therefore, the next three numbers that will be generated are: - 28
- 32 - 36
b) Using an insecure random number generator for cryptographic purposes is problematic be-
cause it introduces predictability in generating cryptographic keys or other sensitive parameters.
If an attacker can predict the numbers being used to generate cryptographic keys, they may be
able to break the encryption scheme and compromise the security of the system. Randomness is
a crucial element in cryptographic protocols to ensure secure communication and protect sensitive
information.
8 9. WEAKNESSES IN HASH FUNCTIONS
Problem 9. Consider a hash function H(x)=(ax +b) mod 11, where a= 3 and b= 5.
a) Calculate H(7).
b) Find an input xsuch that H(x)=6.
c) Determine whether the given hash function is collision-resistant.
Solution 9.
a) To find H(7), substitute x= 7 into the hash function:
H(7) = (3 ·7 + 5) mod 11 = 26 mod 11 = 4
Therefore, H(7) = 4.
b) To find an input xsuch that H(x)=6, set H(x)=6and solve for x:
(3x+ 5) mod 11 = 6
3x+ 5 = 6 ·11 + k, where 0≤k < 11
3x+ 5 = 66 + k
3x= 61 + k
Since kcan take values from 0 to 10, we check for ksuch that (61 + k)is divisible by 3:
k= 1
3x= 62
x=62
3= 202
3
Therefore, an input xsuch that H(x)=6is not an integer.
c) The given hash function is not collision-resistant because multiple inputs can map to the
same output. For example, H(0) = 5 and H(11) = 5, showing a collision.
9 Cryptographic Algorithms and Protocols
Problem 1. Consider a digital signature scheme that uses the RSA algorithm with a modulus
N= 187 and public exponent e= 13. Alice signs a message by raising it to the power of d= 37
(mod 187). If the original message is m= 45, what is the signature that Alice sends?
Solution 1. Given that N= 187,e= 13,d= 37, and m= 45, we can calculate the signature
as follows:
1. Calculate the public key component:
public key = (N, e) = (187,13)
2. Calculate the private key component: Firstly, we need to find pand qsuch that N=p·q= 187.
Through factorization, we find that p= 11 and q= 17. Next, calculate ϕ(N) = (p−1)(q−1) =
10 ·16 = 160. Then, calculate the private key d=e−1(mod ϕ(N)).
d= 13−1(mod 160) = 37
3. Calculate the signature: The signature is calculated as:
signature =md(mod N) = 4537 (mod 187)
signature = 148
Therefore, Alice will send the signature 148 for the message m= 45.
10 11. ISSUES WITH SECURE MULTIPARTY COMPUTATION PROTOCOLS
Problem 11. Consider a secure multiparty computation protocol involving three parties A,B,
and C. Each party has a secret number that they want to compute the sum of without revealing
their individual values. The protocol involves additive secret sharing where each party splits their
secret into two shares and sends one share to each of the other parties. The sum of the three
secret numbers should be computed by combining the shares in a secure manner.
Suppose A’s secret share sent to Bis 5, B’s secret share sent to Cis 3, and C’s secret share
sent to Ais 7.
a) Determine the sum of the three secret numbers without revealing the individual secrets.
b) Discuss any potential security risks or attacks that could compromise the secrecy of the
computed sum.
Solution 11.
a) To compute the sum of the three secret numbers, we can add up all the shares sent between
the parties:
A’s share sent to B(5) + B’s share sent to C(3) + C’s share sent to A(7)=5+3+7=15
Therefore, the sum of the three secret numbers is 15.
b) One potential security risk is collusion between two parties. If two parties collude and share
their secret shares, they can deduce the third secret share and thus compromise the secrecy of
the computed sum. In this case, if Aand Ccollude, they can add their secret shares to obtain B’s
secret share without Bknowing. This would reveal B’s secret and compromise the security of the
protocol.
10.1 12. DIFFICULTY IN ACHIEVING FORWARD SECRECY IN COMMUNICATION
PROTOCOLS
Problem 12. In a communication protocol, Alice and Bob agreed to use the Diffie-Hellman key
exchange algorithm to establish a shared secret key. Alice’s public key is g= 5 and p= 23. Bob’s
public key is g= 7 and p= 23. Given that the secret key (afor Alice and bfor Bob) is 6and 12
respectively, calculate the shared secret key.
Solution 12.
a) Alice calculates (gbmod p)amod pto obtain the shared secret key:
Alice: (76mod 23)12 mod 23
Calculating the values:
(279936 mod 23)12 mod 23
1412 mod 23
1,116,668,081,822,284 mod 23
21
Therefore, the shared secret key for Alice is 21.
b) Bob calculates (gamod p)bmod pto obtain the shared secret key:
Bob: (512 mod 23)6mod 23
Calculating the values:
(244140625 mod 23)6mod 23
186mod 23
34,992,033,553 mod 23
15
Therefore, the shared secret key for Bob is 15.
c) Since both Alice and Bob have calculated their respective shared secret keys, they can now
communicate securely using the Diffie-Hellman key exchange algorithm with a shared key of 15.
I. Problems on Cryptographic Algorithms and Protocols
11 13. CHALLENGES IN IMPLEMENTING HOMOMORPHIC ENCRYPTION
Problem 13. Consider a homomorphic encryption scheme where plaintexts are encoded as
integers mod 26. The encryption function takes a plaintext mand two random numbers r1and
r2to generate the ciphertext: c=m+r1mod 26 + r2mod 26. Suppose we want to perform a
homomorphic multiplication operation on two ciphertexts c1and c2, where c1= 10 and c2= 17.
Calculate the result of the homomorphic multiplication operation.
Solution 13. To perform homomorphic multiplication, we can simply multiply the ciphertexts:
cmul =c1×c2mod 26. Given c1= 10 and c2= 17, we have:
cmul = 10 ×17 mod 26 = 170 mod 26 = 12
Therefore, the result of the homomorphic multiplication operation on ciphertexts c1= 10 and
c2= 17 is cmul = 12.
This concludes the solution to the problem.
12 Cryptographic Algorithms and Protocols
Problem 1. Consider a simple substitution cipher where each letter of the alphabet is replaced
by a different letter. If we have encrypted the message "HELLO" using a substitution cipher and the
encryption key is as follows: {H→Q, E →B, L →X, O →M}, what is the encrypted message?
Problem 2. Alice and Bob want to establish a shared secret key using the Diffie-Hellman key
exchange protocol. If the prime number p= 23 and the primitive root α= 5, Alice chooses her
private key as a= 6 and Bob chooses his private key as b= 15, what is the shared secret key that
they will both compute?
Problem 3. In RSA encryption, if the public key is (n= 77, e = 7) and the message to be
encrypted is m= 13, what is the ciphertext produced using the RSA algorithm?
Solution 1. a) The encrypted message for "HELLO" using the substitution cipher key given
would be "QBXXM".
b) Alice computes her public key as A=αamod p= 56mod 23 = 8. Bob computes his
public key as B=αbmod p= 515 mod 23 = 19. The shared secret key is K=Bamod p= 196
mod 23 = 2.
c) To encrypt the message using RSA encryption, compute c=memod n= 137mod 77 =
16. Therefore, the ciphertext produced is 16.
13 Cryptographic Algorithms and Protocols
Problem 1. Consider a secure communication protocol that uses Diffie-Hellman key exchange
to establish a shared secret key between Alice and Bob. If the prime modulus p= 23 and the base
g= 5, determine the shared secret key when Alice chooses a private key a= 6 and Bob chooses
a private key b= 15.
Solution 1. The shared secret key can be calculated by both Alice and Bob using the following
steps:
a) Alice calculates A=gamod p:
A= 56mod 23 = 25 mod 23 = 2
b) Bob calculates B=gbmod p:
B= 515 mod 23 = 30,517,578,125 mod 23 = 19
c) Alice and Bob share their calculated values Aand B, respectively.
d) Alice calculates the shared secret key: K=Bamod p:
K= 196mod 23 = 47,045,881 mod 23 = 2
e) Bob calculates the shared secret key: K=Abmod p:
K= 215 mod 23 = 32,768 mod 23 = 2
Thus, the shared secret key for both Alice and Bob is 2.
Problem 2. In the RSA encryption algorithm, suppose Alice chooses two prime numbers p= 11
and q= 17 for her public and private keys. She also chooses the public encryption exponent e= 7.
Determine the private decryption exponent d.
Solution 2. To find the private decryption exponent d, we must first calculate the following: -
n=p×q= 11 ×17 = 187 -φ(n)=(p−1) ×(q−1) = 10 ×16 = 160 - Then we solve the equation
e×d≡1 (mod φ(n)) for d:
7d≡1 (mod 160)
Solving this congruence equation, we find d= 23.
I’m happy to help with that. Here is a numerical problem on Cryptographic Algorithms and
Protocols for you:
14 16. PROBLEMS WITH END-TO-END ENCRYPTION SOLUTIONS
Problem 16. Consider a scenario where Alice wants to securely communicate with Bob using end-
to-end encryption. They decide to use the RSA cryptosystem for encryption and decryption. Alice’s
public key is (eA, NA) = (5,143), and her private key is (dA, NA) = (29,143). Bob generates his
own keys where his public key is (eB, NB) = (3,187), and his private key is (dB, NB) = (107,187).
a) If Alice wants to send a message M = 25 to Bob, what is the ciphertext that will be sent over
the network?
b) If Bob receives the ciphertext C = 97 from Alice, what is the original message M that Alice
intended to send him?
Solution 16.
a) To encrypt the message M = 25 using Alice’s public key, we use the encryption function:
C=MeAmod NA
C= 255mod 143
C= 3125 mod 143
C= 49
Therefore, the ciphertext that will be sent over the network is 49.
b) To decrypt the ciphertext C = 97 using Bob’s private key, we use the decryption function:
M=CdBmod NB
M= 97107 mod 187
M= 136904183893900215547781596700000000000000000000000000000000000000000000000000000000000000000 < /br > mod 187
M= 25
Therefore, the original message that Alice intended to send to Bob is 25.
15 17. CHALLENGES IN ACHIEVING SECURE AUTHENTICATION IN DISTRIBUTED SYS-
TEMS
Problem 17. Consider a distributed system where three entities need to authenticate each other
using a challenge-response protocol based on a shared secret key. Entity Agenerates a random
challenge cA= 347, Entity Bgenerates a random challenge cB= 512, and Entity Cgenerates a
random challenge cC= 635. The shared secret key between all entities is K= 123.
a) Entity Asends cAto Entity B, who responds with the result of cA⊕K. Calculate the response
sent by Entity Bto Entity A.
b) Entity Bsends cBto Entity C, who responds with the result of cB⊕K. Calculate the response
sent by Entity Cto Entity B.
c) Entity Csends cCto Entity A, who responds with the result of cC⊕K. Calculate the response
sent by Entity Ato Entity C.
Solution 17.
a) Entity Bcalculates the response as cA⊕K:
cA⊕K= 347 ⊕123 = 224
Therefore, Entity Bsends the response 224 to Entity A.
b) Entity Ccalculates the response as cB⊕K:
cB⊕K= 512 ⊕123 = 635
Therefore, Entity Csends the response 635 to Entity B.
c) Entity Acalculates the response as cC⊕K:
cC⊕K= 635 ⊕123 = 756
Therefore, Entity Asends the response 756 to Entity C.
16 Cryptographic Algorithms and Protocols
Problem: Alice wants to securely send a message to Bob using symmetric encryption. She
chooses the block cipher AES with a key size of 128 bits. The message she wants to send is 1280
bits long.
a) How many blocks will the message be divided into for encryption using AES?
b) If Alice and Bob are using the Electronic Code Book (ECB) mode, explain what kind of
vulnerability may arise in this scenario.
Solution:
a) The AES block size is 128 bits (16 bytes), so the 1280-bit message will need to be divided
into blocks of size 128 bits each.
Number of blocks = Message size / Block size = 1280 bits / 128 bits = 10 blocks
Therefore, the message will be divided into 10 blocks for encryption using AES.
b) In the ECB mode, each block of plaintext is encrypted separately with the same key. This
means that identical plaintext blocks will result in identical ciphertext blocks. This vulnerability can
be exploited by an attacker to detect patterns in the encrypted data, potentially revealing information
or relationships within the message. Additionally, ECB does not provide semantic security, so it
may leak information even if the plaintext is encrypted.
In the given scenario, if Alice sends any message that contains repeated blocks of plaintext
(e.g., patterns, images, or repeated phrases), an attacker can identify these repetitions and poten-
tially infer information about the message’s content.
I am unable to provide numerical problem questions and solutions for Cryptographic Algorithms
and Protocols at the moment. Would you like me to assist you with theoretical concepts or any other
form of assistance related to this topic?
I can certainly provide a problem and solution for you!
17 Cryptographic Algorithms and Protocols
Problem:
Consider the following scenario in a public-key encryption system using RSA:
Alice wants to send a confidential message to Bob. Bob has a public encryption key (e, n) =
(17,323) and a private key (d, n) = (275,323). Alice encrypts her message as follows: she repre-
sents the message as a number where each letter is assigned a value (A=1, B=2, ..., Z=26), and
then raises this number to the power of the public key (e)modulo nto obtain the ciphertext.
Alice’s message is "HELLO". The numerical representation of this message is [8, 5, 12, 12,
15]. Calculate the ciphertext that Alice will send to Bob.
Solution:
To find the ciphertext for the message "HELLO", we will encrypt each letter separately and
combine the results.
Let’s encode each letter:
H: 8 E: 5 L: 12 L: 12 O: 15
For letter "H": 817 ≡106 (mod 323)
For letter "E": 517 ≡9 (mod 323)
For letter "L": 1217 ≡144 (mod 323)
For the second "L": 1217 ≡144 (mod 323)
For letter "O": 1517 ≡21 (mod 323)
Now, combine these ciphertext values: 1069194144214421
Therefore, the ciphertext that Alice will send to Bob for the message "HELLO" is 10691941442144.
3 3. VULNERABILITIES IN ASYMMETRIC ENCRYPTION SCHEMES
Problem 3. Consider the RSA encryption scheme with public key (e, N) = (7,187). An attacker
intercepts a message m= 65 encrypted using this public key.
a) Compute the private key d.
b) Determine the decrypted message.
Solution 3.
a) To compute the private key d, we need to find the value such that ed ≡1 (mod φ(N)), where
φ(N)is Euler’s totient function.
Given that N= 187, we first need to calculate φ(N):
φ(N)=(p−1)(q−1) = 10 ×18 = 180.
Next, we solve for d:
7d≡1 (mod 180).
Solving this congruence, we get d= 103.
b) To decrypt the message, we calculate cd(mod N), where cis the intercepted ciphertext.
m= 65103 (mod 187).
Using fast modular exponentiation, we can simplify this calculation:
652≡52 (mod 187),
654≡522≡64 (mod 187),
658≡642≡141 (mod 187),
6516 ≡1412≡145 (mod 187),
6532 ≡1452≡79 (mod 187),
6564 ≡792≡77 (mod 187).
Therefore,
65103 ≡65 ×6532 ×6516 ×652×651
≡65 ×79 ×145 ×52
≡64 (mod 187).
Hence, the decrypted message is m= 64.
4 4. CRYPTANALYSIS OF SYMMETRIC KEY ALGORITHMS
Problem 4. Consider a block cipher with a block size of 64 bits and a key size of 128 bits. An
attacker performs a known-plaintext attack where they obtain 10 plaintext-ciphertext pairs. Each
pair has a plaintext of 64 bits and a corresponding ciphertext of 64 bits. The attacker wants to
determine the key using this information.
a) What is the maximum number of key candidates that the attacker needs to try to recover the
key using exhaustive search?
b) If the attacker has 2 plaintext-ciphertext pairs chosen by themselves (not obtained from
known plaintext) and wants to use a chosen-plaintext attack, how many queries do they need to
make to uniquely determine the key?
Solution 4.
a) Since the key size is 128 bits, the total number of possible keys is 2128. With the given 10
plaintext-ciphertext pairs, the attacker needs to try each key candidate against all pairs. Therefore,
the maximum number of key candidates to try is 2128 = 340,282,366,920,938,463,463,374,607,431,768,211,456.
b) In a chosen-plaintext attack, the attacker can choose their plaintexts. With 2 plaintext-
ciphertext pairs, each pair contributes 64 bits of information about the key (block size). Since
the key size is 128 bits, the attacker needs a total of 128/64 = 2 pairs to uniquely determine the
key. Therefore, the attacker needs to make a total of 2 queries.
I. Problem:
Consider a side-channel attack on a symmetric encryption algorithm that leaks information
about the encryption key based on the power consumption during encryption. Suppose you have
the following data:
- Power consumption when encrypting the plaintext 0x45: 100 units - Power consumption when
encrypting the plaintext 0xAF: 150 units
Assume that the power consumption is directly related to the number of bit changes in the
encryption key during encryption.
a) Determine the Hamming distance (number of differing bits) between the encryption keys
used for encrypting the plaintexts 0x45 and 0xAF.
b) If the encryption key consists of 8 bits, find the average power consumption when encrypting
a plaintext using this encryption algorithm.
Solution:
a) To find the Hamming distance between the encryption keys used for the two plaintexts:
0x45 =0100 0101
0xAF =1010 1111
The Hamming distance is the number of bit positions in which the two binary strings differ:
Hamming distance = 3 (bits that differ are in positions 2, 5, and 7)
b) With an 8-bit key, each bit change contributes to the power consumption. From part a, we
calculated three differing bits in the encryption key. Thus, the average power consumption when
encrypting a plaintext is:
Average power consumption =Total power consumption
Number of bit changes =100+150
3=250
3≈83.33 units
Therefore, the average power consumption when encrypting a plaintext using this encryption
algorithm is approximately 83.33 units.
5 6. LACK OF PROTECTION AGAINST QUANTUM COMPUTING THREATS
Problem 6. Consider the Shor’s algorithm for integer factorization. Given N= 15, find the
prime factors of Nusing Shor’s algorithm.
Solution 6. a) According to Shor’s algorithm, we need to find the period of the function f(x) =
axmod N, where a= 2.
Let’s find the period:
•f(0) = 20mod 15 = 1
•f(1) = 21mod 15 = 2
•f(2) = 22mod 15 = 4
•f(3) = 23mod 15 = 8
•f(4) = 24mod 15 = 1
The smallest period is r= 4. We need to find a1= 2(r/2) mod 15. Since r= 4,a1= 22
mod 15 = 4.
Next, we solve the equation gcd(ar/2±1, N). Either gcd(4 + 1,15) or gcd(4 −1,15).
•gcd(5,15) = 5 is a factor of N.
Therefore, the prime factors of N= 15 are 5and 3.
Thus, the prime factors of Nare 3and 5.
b) In this part, we find the same prime factors of N= 15 using the general approach. We
factorize 15 to prime numbers: 15 = 3 ×5.
c) Compare the results obtained from Shor’s algorithm and the general approach.
The results from Shor’s algorithm (3and 5) and the general approach (3and 5) are the same,
confirming the accuracy of both methods.
6 7. RISK OF COLLUSION ATTACKS ON CRYPTOGRAPHIC SYSTEMS
Problem 7. Consider a cryptographic system that uses a key exchange protocol with npartic-
ipants. Each participant holds a secret key that is randomly generated. If kparticipants collude to
share their secret keys, what is the probability that the colluding participants can decrypt a message
encrypted using the system?
Assume that the system is secure as long as at least one participant’s key remains secret.
Solution 7.
To find the probability that the colluding participants can decrypt the message, we need to
calculate the probability that all kparticipants’ keys are shared.
Let’s denote the total number of participants as nand the number of colluding participants as
k. The probability that all kparticipants’ keys are shared can be calculated as follows:
a) Probability that the first participant’s key is shared: k
n
b) Probability that the second participant’s key is shared given that the first participant’s key is
shared: k−1
n−1
c) Probability that the k-th participant’s key is shared given that the previous k−1participants’
keys are shared: k−(k−1)
n−(k−1) =1
n−(k−1)
Therefore, the overall probability that all kparticipants’ keys are shared is:
P(All kkeys are shared) = k
n×k−1
n−1×. . . ×1
n−(k−1)
Substitute n= 10 and k= 3 into the formula:
P(All 3keys are shared) = 3
10 ×2
9×1
8=1
120
Therefore, the probability that the colluding participants can decrypt the message is 1
120 .
7 8. INSECURE RANDOM NUMBER GENERATION IN CRYPTOGRAPHIC ALGORITHMS
Problem 8. Consider a scenario where a cryptographic algorithm requires generating random
numbers for secure key generation. However, the random number generator used is insecure and
produces predictable outputs.
Assume the insecure random number generator outputs a sequence of numbers as follows: 4,
8, 12, 16, 20, 24, ...
a) Calculate the next three numbers that will be generated by this insecure random number
generator.
b) Explain why using such an insecure random number generator for cryptographic purposes
is problematic.
Solution 8.
a) The pattern observed in the sequence of numbers generated by the insecure random number
generator is incrementing by 4. Therefore, the next three numbers that will be generated are: - 28
- 32 - 36
b) Using an insecure random number generator for cryptographic purposes is problematic be-
cause it introduces predictability in generating cryptographic keys or other sensitive parameters.
If an attacker can predict the numbers being used to generate cryptographic keys, they may be
able to break the encryption scheme and compromise the security of the system. Randomness is
a crucial element in cryptographic protocols to ensure secure communication and protect sensitive
information.
8 9. WEAKNESSES IN HASH FUNCTIONS
Problem 9. Consider a hash function H(x)=(ax +b) mod 11, where a= 3 and b= 5.
a) Calculate H(7).
b) Find an input xsuch that H(x)=6.
c) Determine whether the given hash function is collision-resistant.
Solution 9.
a) To find H(7), substitute x= 7 into the hash function:
H(7) = (3 ·7 + 5) mod 11 = 26 mod 11 = 4
Therefore, H(7) = 4.
b) To find an input xsuch that H(x)=6, set H(x)=6and solve for x:
(3x+ 5) mod 11 = 6
3x+ 5 = 6 ·11 + k, where 0≤k < 11
3x+ 5 = 66 + k
3x= 61 + k
Since kcan take values from 0 to 10, we check for ksuch that (61 + k)is divisible by 3:
k= 1
3x= 62
x=62
3= 202
3
Therefore, an input xsuch that H(x)=6is not an integer.
c) The given hash function is not collision-resistant because multiple inputs can map to the
same output. For example, H(0) = 5 and H(11) = 5, showing a collision.
9 Cryptographic Algorithms and Protocols
Problem 1. Consider a digital signature scheme that uses the RSA algorithm with a modulus
N= 187 and public exponent e= 13. Alice signs a message by raising it to the power of d= 37
(mod 187). If the original message is m= 45, what is the signature that Alice sends?
Solution 1. Given that N= 187,e= 13,d= 37, and m= 45, we can calculate the signature
as follows:
1. Calculate the public key component:
public key = (N, e) = (187,13)
2. Calculate the private key component: Firstly, we need to find pand qsuch that N=p·q= 187.
Through factorization, we find that p= 11 and q= 17. Next, calculate ϕ(N) = (p−1)(q−1) =
10 ·16 = 160. Then, calculate the private key d=e−1(mod ϕ(N)).
d= 13−1(mod 160) = 37
3. Calculate the signature: The signature is calculated as:
signature =md(mod N) = 4537 (mod 187)
signature = 148
Therefore, Alice will send the signature 148 for the message m= 45.
10 11. ISSUES WITH SECURE MULTIPARTY COMPUTATION PROTOCOLS
Problem 11. Consider a secure multiparty computation protocol involving three parties A,B,
and C. Each party has a secret number that they want to compute the sum of without revealing
their individual values. The protocol involves additive secret sharing where each party splits their
secret into two shares and sends one share to each of the other parties. The sum of the three
secret numbers should be computed by combining the shares in a secure manner.
Suppose A’s secret share sent to Bis 5, B’s secret share sent to Cis 3, and C’s secret share
sent to Ais 7.
a) Determine the sum of the three secret numbers without revealing the individual secrets.
b) Discuss any potential security risks or attacks that could compromise the secrecy of the
computed sum.
Solution 11.
a) To compute the sum of the three secret numbers, we can add up all the shares sent between
the parties:
A’s share sent to B(5) + B’s share sent to C(3) + C’s share sent to A(7)=5+3+7=15
Therefore, the sum of the three secret numbers is 15.
b) One potential security risk is collusion between two parties. If two parties collude and share
their secret shares, they can deduce the third secret share and thus compromise the secrecy of
the computed sum. In this case, if Aand Ccollude, they can add their secret shares to obtain B’s
secret share without Bknowing. This would reveal B’s secret and compromise the security of the
protocol.
10.1 12. DIFFICULTY IN ACHIEVING FORWARD SECRECY IN COMMUNICATION
PROTOCOLS
Problem 12. In a communication protocol, Alice and Bob agreed to use the Diffie-Hellman key
exchange algorithm to establish a shared secret key. Alice’s public key is g= 5 and p= 23. Bob’s
public key is g= 7 and p= 23. Given that the secret key (afor Alice and bfor Bob) is 6and 12
respectively, calculate the shared secret key.
Solution 12.
a) Alice calculates (gbmod p)amod pto obtain the shared secret key:
Alice: (76mod 23)12 mod 23
Calculating the values:
(279936 mod 23)12 mod 23
1412 mod 23
1,116,668,081,822,284 mod 23
21
Therefore, the shared secret key for Alice is 21.
b) Bob calculates (gamod p)bmod pto obtain the shared secret key:
Bob: (512 mod 23)6mod 23
Calculating the values:
(244140625 mod 23)6mod 23
186mod 23
34,992,033,553 mod 23
15
Therefore, the shared secret key for Bob is 15.
c) Since both Alice and Bob have calculated their respective shared secret keys, they can now
communicate securely using the Diffie-Hellman key exchange algorithm with a shared key of 15.
I. Problems on Cryptographic Algorithms and Protocols
11 13. CHALLENGES IN IMPLEMENTING HOMOMORPHIC ENCRYPTION
Problem 13. Consider a homomorphic encryption scheme where plaintexts are encoded as
integers mod 26. The encryption function takes a plaintext mand two random numbers r1and
r2to generate the ciphertext: c=m+r1mod 26 + r2mod 26. Suppose we want to perform a
homomorphic multiplication operation on two ciphertexts c1and c2, where c1= 10 and c2= 17.
Calculate the result of the homomorphic multiplication operation.
Solution 13. To perform homomorphic multiplication, we can simply multiply the ciphertexts:
cmul =c1×c2mod 26. Given c1= 10 and c2= 17, we have:
cmul = 10 ×17 mod 26 = 170 mod 26 = 12
Therefore, the result of the homomorphic multiplication operation on ciphertexts c1= 10 and
c2= 17 is cmul = 12.
This concludes the solution to the problem.
12 Cryptographic Algorithms and Protocols
Problem 1. Consider a simple substitution cipher where each letter of the alphabet is replaced
by a different letter. If we have encrypted the message "HELLO" using a substitution cipher and the
encryption key is as follows: {H→Q, E →B, L →X, O →M}, what is the encrypted message?
Problem 2. Alice and Bob want to establish a shared secret key using the Diffie-Hellman key
exchange protocol. If the prime number p= 23 and the primitive root α= 5, Alice chooses her
private key as a= 6 and Bob chooses his private key as b= 15, what is the shared secret key that
they will both compute?
Problem 3. In RSA encryption, if the public key is (n= 77, e = 7) and the message to be
encrypted is m= 13, what is the ciphertext produced using the RSA algorithm?
Solution 1. a) The encrypted message for "HELLO" using the substitution cipher key given
would be "QBXXM".
b) Alice computes her public key as A=αamod p= 56mod 23 = 8. Bob computes his
public key as B=αbmod p= 515 mod 23 = 19. The shared secret key is K=Bamod p= 196
mod 23 = 2.
c) To encrypt the message using RSA encryption, compute c=memod n= 137mod 77 =
16. Therefore, the ciphertext produced is 16.
13 Cryptographic Algorithms and Protocols
Problem 1. Consider a secure communication protocol that uses Diffie-Hellman key exchange
to establish a shared secret key between Alice and Bob. If the prime modulus p= 23 and the base
g= 5, determine the shared secret key when Alice chooses a private key a= 6 and Bob chooses
a private key b= 15.
Solution 1. The shared secret key can be calculated by both Alice and Bob using the following
steps:
a) Alice calculates A=gamod p:
A= 56mod 23 = 25 mod 23 = 2
b) Bob calculates B=gbmod p:
B= 515 mod 23 = 30,517,578,125 mod 23 = 19
c) Alice and Bob share their calculated values Aand B, respectively.
d) Alice calculates the shared secret key: K=Bamod p:
K= 196mod 23 = 47,045,881 mod 23 = 2
e) Bob calculates the shared secret key: K=Abmod p:
K= 215 mod 23 = 32,768 mod 23 = 2
Thus, the shared secret key for both Alice and Bob is 2.
Problem 2. In the RSA encryption algorithm, suppose Alice chooses two prime numbers p= 11
and q= 17 for her public and private keys. She also chooses the public encryption exponent e= 7.
Determine the private decryption exponent d.
Solution 2. To find the private decryption exponent d, we must first calculate the following: -
n=p×q= 11 ×17 = 187 -φ(n)=(p−1) ×(q−1) = 10 ×16 = 160 - Then we solve the equation
e×d≡1 (mod φ(n)) for d:
7d≡1 (mod 160)
Solving this congruence equation, we find d= 23.
I’m happy to help with that. Here is a numerical problem on Cryptographic Algorithms and
Protocols for you:
14 16. PROBLEMS WITH END-TO-END ENCRYPTION SOLUTIONS
Problem 16. Consider a scenario where Alice wants to securely communicate with Bob using end-
to-end encryption. They decide to use the RSA cryptosystem for encryption and decryption. Alice’s
public key is (eA, NA) = (5,143), and her private key is (dA, NA) = (29,143). Bob generates his
own keys where his public key is (eB, NB) = (3,187), and his private key is (dB, NB) = (107,187).
a) If Alice wants to send a message M = 25 to Bob, what is the ciphertext that will be sent over
the network?
b) If Bob receives the ciphertext C = 97 from Alice, what is the original message M that Alice
intended to send him?
Solution 16.
a) To encrypt the message M = 25 using Alice’s public key, we use the encryption function:
C=MeAmod NA
C= 255mod 143
C= 3125 mod 143
C= 49
Therefore, the ciphertext that will be sent over the network is 49.
b) To decrypt the ciphertext C = 97 using Bob’s private key, we use the decryption function:
M=CdBmod NB
M= 97107 mod 187
M= 136904183893900215547781596700000000000000000000000000000000000000000000000000000000000000000 < /br > mod 187
M= 25
Therefore, the original message that Alice intended to send to Bob is 25.
15 17. CHALLENGES IN ACHIEVING SECURE AUTHENTICATION IN DISTRIBUTED SYS-
TEMS
Problem 17. Consider a distributed system where three entities need to authenticate each other
using a challenge-response protocol based on a shared secret key. Entity Agenerates a random
challenge cA= 347, Entity Bgenerates a random challenge cB= 512, and Entity Cgenerates a
random challenge cC= 635. The shared secret key between all entities is K= 123.
a) Entity Asends cAto Entity B, who responds with the result of cA⊕K. Calculate the response
sent by Entity Bto Entity A.
b) Entity Bsends cBto Entity C, who responds with the result of cB⊕K. Calculate the response
sent by Entity Cto Entity B.
c) Entity Csends cCto Entity A, who responds with the result of cC⊕K. Calculate the response
sent by Entity Ato Entity C.
Solution 17.
a) Entity Bcalculates the response as cA⊕K:
cA⊕K= 347 ⊕123 = 224
Therefore, Entity Bsends the response 224 to Entity A.
b) Entity Ccalculates the response as cB⊕K:
cB⊕K= 512 ⊕123 = 635
Therefore, Entity Csends the response 635 to Entity B.
c) Entity Acalculates the response as cC⊕K:
cC⊕K= 635 ⊕123 = 756
Therefore, Entity Asends the response 756 to Entity C.
16 Cryptographic Algorithms and Protocols
Problem: Alice wants to securely send a message to Bob using symmetric encryption. She
chooses the block cipher AES with a key size of 128 bits. The message she wants to send is 1280
bits long.
a) How many blocks will the message be divided into for encryption using AES?
b) If Alice and Bob are using the Electronic Code Book (ECB) mode, explain what kind of
vulnerability may arise in this scenario.
Solution:
a) The AES block size is 128 bits (16 bytes), so the 1280-bit message will need to be divided
into blocks of size 128 bits each.
Number of blocks = Message size / Block size = 1280 bits / 128 bits = 10 blocks
Therefore, the message will be divided into 10 blocks for encryption using AES.
b) In the ECB mode, each block of plaintext is encrypted separately with the same key. This
means that identical plaintext blocks will result in identical ciphertext blocks. This vulnerability can
be exploited by an attacker to detect patterns in the encrypted data, potentially revealing information
or relationships within the message. Additionally, ECB does not provide semantic security, so it
may leak information even if the plaintext is encrypted.
In the given scenario, if Alice sends any message that contains repeated blocks of plaintext
(e.g., patterns, images, or repeated phrases), an attacker can identify these repetitions and poten-
tially infer information about the message’s content.
I am unable to provide numerical problem questions and solutions for Cryptographic Algorithms
and Protocols at the moment. Would you like me to assist you with theoretical concepts or any other
form of assistance related to this topic?
I can certainly provide a problem and solution for you!
17 Cryptographic Algorithms and Protocols
Problem:
Consider the following scenario in a public-key encryption system using RSA:
Alice wants to send a confidential message to Bob. Bob has a public encryption key (e, n) =
(17,323) and a private key (d, n) = (275,323). Alice encrypts her message as follows: she repre-
sents the message as a number where each letter is assigned a value (A=1, B=2, ..., Z=26), and
then raises this number to the power of the public key (e)modulo nto obtain the ciphertext.
Alice’s message is "HELLO". The numerical representation of this message is [8, 5, 12, 12,
15]. Calculate the ciphertext that Alice will send to Bob.
Solution:
To find the ciphertext for the message "HELLO", we will encrypt each letter separately and
combine the results.
Let’s encode each letter:
H: 8 E: 5 L: 12 L: 12 O: 15
For letter "H": 817 ≡106 (mod 323)
For letter "E": 517 ≡9 (mod 323)
For letter "L": 1217 ≡144 (mod 323)
For the second "L": 1217 ≡144 (mod 323)
For letter "O": 1517 ≡21 (mod 323)
Now, combine these ciphertext values: 1069194144214421
Therefore, the ciphertext that Alice will send to Bob for the message "HELLO" is 10691941442144.
3 3. VULNERABILITIES IN ASYMMETRIC ENCRYPTION SCHEMES
Problem 3. Consider the RSA encryption scheme with public key (e, N) = (7,187). An attacker
intercepts a message m= 65 encrypted using this public key.
a) Compute the private key d.
b) Determine the decrypted message.
Solution 3.
a) To compute the private key d, we need to find the value such that ed ≡1 (mod φ(N)), where
φ(N)is Euler’s totient function.
Given that N= 187, we first need to calculate φ(N):
φ(N)=(p−1)(q−1) = 10 ×18 = 180.
Next, we solve for d:
7d≡1 (mod 180).
Solving this congruence, we get d= 103.
b) To decrypt the message, we calculate cd(mod N), where cis the intercepted ciphertext.
m= 65103 (mod 187).
Using fast modular exponentiation, we can simplify this calculation:
652≡52 (mod 187),
654≡522≡64 (mod 187),
658≡642≡141 (mod 187),
6516 ≡1412≡145 (mod 187),
6532 ≡1452≡79 (mod 187),
6564 ≡792≡77 (mod 187).
Therefore,
65103 ≡65 ×6532 ×6516 ×652×651
≡65 ×79 ×145 ×52
≡64 (mod 187).
Hence, the decrypted message is m= 64.
4 4. CRYPTANALYSIS OF SYMMETRIC KEY ALGORITHMS
Problem 4. Consider a block cipher with a block size of 64 bits and a key size of 128 bits. An
attacker performs a known-plaintext attack where they obtain 10 plaintext-ciphertext pairs. Each
pair has a plaintext of 64 bits and a corresponding ciphertext of 64 bits. The attacker wants to
determine the key using this information.
a) What is the maximum number of key candidates that the attacker needs to try to recover the
key using exhaustive search?
b) If the attacker has 2 plaintext-ciphertext pairs chosen by themselves (not obtained from
known plaintext) and wants to use a chosen-plaintext attack, how many queries do they need to
make to uniquely determine the key?
Solution 4.
a) Since the key size is 128 bits, the total number of possible keys is 2128. With the given 10
plaintext-ciphertext pairs, the attacker needs to try each key candidate against all pairs. Therefore,
the maximum number of key candidates to try is 2128 = 340,282,366,920,938,463,463,374,607,431,768,211,456.
b) In a chosen-plaintext attack, the attacker can choose their plaintexts. With 2 plaintext-
ciphertext pairs, each pair contributes 64 bits of information about the key (block size). Since
the key size is 128 bits, the attacker needs a total of 128/64 = 2 pairs to uniquely determine the
key. Therefore, the attacker needs to make a total of 2 queries.
I. Problem:
Consider a side-channel attack on a symmetric encryption algorithm that leaks information
about the encryption key based on the power consumption during encryption. Suppose you have
the following data:
- Power consumption when encrypting the plaintext 0x45: 100 units - Power consumption when
encrypting the plaintext 0xAF: 150 units
Assume that the power consumption is directly related to the number of bit changes in the
encryption key during encryption.
a) Determine the Hamming distance (number of differing bits) between the encryption keys
used for encrypting the plaintexts 0x45 and 0xAF.
b) If the encryption key consists of 8 bits, find the average power consumption when encrypting
a plaintext using this encryption algorithm.
Solution:
a) To find the Hamming distance between the encryption keys used for the two plaintexts:
0x45 =0100 0101
0xAF =1010 1111
The Hamming distance is the number of bit positions in which the two binary strings differ:
Hamming distance = 3 (bits that differ are in positions 2, 5, and 7)
b) With an 8-bit key, each bit change contributes to the power consumption. From part a, we
calculated three differing bits in the encryption key. Thus, the average power consumption when
encrypting a plaintext is:
Average power consumption =Total power consumption
Number of bit changes =100+150
3=250
3≈83.33 units
Therefore, the average power consumption when encrypting a plaintext using this encryption
algorithm is approximately 83.33 units.
5 6. LACK OF PROTECTION AGAINST QUANTUM COMPUTING THREATS
Problem 6. Consider the Shor’s algorithm for integer factorization. Given N= 15, find the
prime factors of Nusing Shor’s algorithm.
Solution 6. a) According to Shor’s algorithm, we need to find the period of the function f(x) =
axmod N, where a= 2.
Let’s find the period:
•f(0) = 20mod 15 = 1
•f(1) = 21mod 15 = 2
•f(2) = 22mod 15 = 4
•f(3) = 23mod 15 = 8
•f(4) = 24mod 15 = 1
The smallest period is r= 4. We need to find a1= 2(r/2) mod 15. Since r= 4,a1= 22
mod 15 = 4.
Next, we solve the equation gcd(ar/2±1, N). Either gcd(4 + 1,15) or gcd(4 −1,15).
•gcd(5,15) = 5 is a factor of N.
Therefore, the prime factors of N= 15 are 5and 3.
Thus, the prime factors of Nare 3and 5.
b) In this part, we find the same prime factors of N= 15 using the general approach. We
factorize 15 to prime numbers: 15 = 3 ×5.
c) Compare the results obtained from Shor’s algorithm and the general approach.
The results from Shor’s algorithm (3and 5) and the general approach (3and 5) are the same,
confirming the accuracy of both methods.
6 7. RISK OF COLLUSION ATTACKS ON CRYPTOGRAPHIC SYSTEMS
Problem 7. Consider a cryptographic system that uses a key exchange protocol with npartic-
ipants. Each participant holds a secret key that is randomly generated. If kparticipants collude to
share their secret keys, what is the probability that the colluding participants can decrypt a message
encrypted using the system?
Assume that the system is secure as long as at least one participant’s key remains secret.
Solution 7.
To find the probability that the colluding participants can decrypt the message, we need to
calculate the probability that all kparticipants’ keys are shared.
Let’s denote the total number of participants as nand the number of colluding participants as
k. The probability that all kparticipants’ keys are shared can be calculated as follows:
a) Probability that the first participant’s key is shared: k
n
b) Probability that the second participant’s key is shared given that the first participant’s key is
shared: k−1
n−1
c) Probability that the k-th participant’s key is shared given that the previous k−1participants’
keys are shared: k−(k−1)
n−(k−1) =1
n−(k−1)
Therefore, the overall probability that all kparticipants’ keys are shared is:
P(All kkeys are shared) = k
n×k−1
n−1×. . . ×1
n−(k−1)
Substitute n= 10 and k= 3 into the formula:
P(All 3keys are shared) = 3
10 ×2
9×1
8=1
120
Therefore, the probability that the colluding participants can decrypt the message is 1
120 .
7 8. INSECURE RANDOM NUMBER GENERATION IN CRYPTOGRAPHIC ALGORITHMS
Problem 8. Consider a scenario where a cryptographic algorithm requires generating random
numbers for secure key generation. However, the random number generator used is insecure and
produces predictable outputs.
Assume the insecure random number generator outputs a sequence of numbers as follows: 4,
8, 12, 16, 20, 24, ...
a) Calculate the next three numbers that will be generated by this insecure random number
generator.
b) Explain why using such an insecure random number generator for cryptographic purposes
is problematic.
Solution 8.
a) The pattern observed in the sequence of numbers generated by the insecure random number
generator is incrementing by 4. Therefore, the next three numbers that will be generated are: - 28
- 32 - 36
b) Using an insecure random number generator for cryptographic purposes is problematic be-
cause it introduces predictability in generating cryptographic keys or other sensitive parameters.
If an attacker can predict the numbers being used to generate cryptographic keys, they may be
able to break the encryption scheme and compromise the security of the system. Randomness is
a crucial element in cryptographic protocols to ensure secure communication and protect sensitive
information.
8 9. WEAKNESSES IN HASH FUNCTIONS
Problem 9. Consider a hash function H(x)=(ax +b) mod 11, where a= 3 and b= 5.
a) Calculate H(7).
b) Find an input xsuch that H(x)=6.
c) Determine whether the given hash function is collision-resistant.
Solution 9.
a) To find H(7), substitute x= 7 into the hash function:
H(7) = (3 ·7 + 5) mod 11 = 26 mod 11 = 4
Therefore, H(7) = 4.
b) To find an input xsuch that H(x)=6, set H(x)=6and solve for x:
(3x+ 5) mod 11 = 6
3x+ 5 = 6 ·11 + k, where 0≤k < 11
3x+ 5 = 66 + k
3x= 61 + k
Since kcan take values from 0 to 10, we check for ksuch that (61 + k)is divisible by 3:
k= 1
3x= 62
x=62
3= 202
3
Therefore, an input xsuch that H(x)=6is not an integer.
c) The given hash function is not collision-resistant because multiple inputs can map to the
same output. For example, H(0) = 5 and H(11) = 5, showing a collision.
9 Cryptographic Algorithms and Protocols
Problem 1. Consider a digital signature scheme that uses the RSA algorithm with a modulus
N= 187 and public exponent e= 13. Alice signs a message by raising it to the power of d= 37
(mod 187). If the original message is m= 45, what is the signature that Alice sends?
Solution 1. Given that N= 187,e= 13,d= 37, and m= 45, we can calculate the signature
as follows:
1. Calculate the public key component:
public key = (N, e) = (187,13)
2. Calculate the private key component: Firstly, we need to find pand qsuch that N=p·q= 187.
Through factorization, we find that p= 11 and q= 17. Next, calculate ϕ(N) = (p−1)(q−1) =
10 ·16 = 160. Then, calculate the private key d=e−1(mod ϕ(N)).
d= 13−1(mod 160) = 37
3. Calculate the signature: The signature is calculated as:
signature =md(mod N) = 4537 (mod 187)
signature = 148
Therefore, Alice will send the signature 148 for the message m= 45.
10 11. ISSUES WITH SECURE MULTIPARTY COMPUTATION PROTOCOLS
Problem 11. Consider a secure multiparty computation protocol involving three parties A,B,
and C. Each party has a secret number that they want to compute the sum of without revealing
their individual values. The protocol involves additive secret sharing where each party splits their
secret into two shares and sends one share to each of the other parties. The sum of the three
secret numbers should be computed by combining the shares in a secure manner.
Suppose A’s secret share sent to Bis 5, B’s secret share sent to Cis 3, and C’s secret share
sent to Ais 7.
a) Determine the sum of the three secret numbers without revealing the individual secrets.
b) Discuss any potential security risks or attacks that could compromise the secrecy of the
computed sum.
Solution 11.
a) To compute the sum of the three secret numbers, we can add up all the shares sent between
the parties:
A’s share sent to B(5) + B’s share sent to C(3) + C’s share sent to A(7)=5+3+7=15
Therefore, the sum of the three secret numbers is 15.
b) One potential security risk is collusion between two parties. If two parties collude and share
their secret shares, they can deduce the third secret share and thus compromise the secrecy of
the computed sum. In this case, if Aand Ccollude, they can add their secret shares to obtain B’s
secret share without Bknowing. This would reveal B’s secret and compromise the security of the
protocol.
10.1 12. DIFFICULTY IN ACHIEVING FORWARD SECRECY IN COMMUNICATION
PROTOCOLS
Problem 12. In a communication protocol, Alice and Bob agreed to use the Diffie-Hellman key
exchange algorithm to establish a shared secret key. Alice’s public key is g= 5 and p= 23. Bob’s
public key is g= 7 and p= 23. Given that the secret key (afor Alice and bfor Bob) is 6and 12
respectively, calculate the shared secret key.
Solution 12.
a) Alice calculates (gbmod p)amod pto obtain the shared secret key:
Alice: (76mod 23)12 mod 23
Calculating the values:
(279936 mod 23)12 mod 23
1412 mod 23
1,116,668,081,822,284 mod 23
21
Therefore, the shared secret key for Alice is 21.
b) Bob calculates (gamod p)bmod pto obtain the shared secret key:
Bob: (512 mod 23)6mod 23
Calculating the values:
(244140625 mod 23)6mod 23
186mod 23
34,992,033,553 mod 23
15
Therefore, the shared secret key for Bob is 15.
c) Since both Alice and Bob have calculated their respective shared secret keys, they can now
communicate securely using the Diffie-Hellman key exchange algorithm with a shared key of 15.
I. Problems on Cryptographic Algorithms and Protocols
11 13. CHALLENGES IN IMPLEMENTING HOMOMORPHIC ENCRYPTION
Problem 13. Consider a homomorphic encryption scheme where plaintexts are encoded as
integers mod 26. The encryption function takes a plaintext mand two random numbers r1and
r2to generate the ciphertext: c=m+r1mod 26 + r2mod 26. Suppose we want to perform a
homomorphic multiplication operation on two ciphertexts c1and c2, where c1= 10 and c2= 17.
Calculate the result of the homomorphic multiplication operation.
Solution 13. To perform homomorphic multiplication, we can simply multiply the ciphertexts:
cmul =c1×c2mod 26. Given c1= 10 and c2= 17, we have:
cmul = 10 ×17 mod 26 = 170 mod 26 = 12
Therefore, the result of the homomorphic multiplication operation on ciphertexts c1= 10 and
c2= 17 is cmul = 12.
This concludes the solution to the problem.
12 Cryptographic Algorithms and Protocols
Problem 1. Consider a simple substitution cipher where each letter of the alphabet is replaced
by a different letter. If we have encrypted the message "HELLO" using a substitution cipher and the
encryption key is as follows: {H→Q, E →B, L →X, O →M}, what is the encrypted message?
Problem 2. Alice and Bob want to establish a shared secret key using the Diffie-Hellman key
exchange protocol. If the prime number p= 23 and the primitive root α= 5, Alice chooses her
private key as a= 6 and Bob chooses his private key as b= 15, what is the shared secret key that
they will both compute?
Problem 3. In RSA encryption, if the public key is (n= 77, e = 7) and the message to be
encrypted is m= 13, what is the ciphertext produced using the RSA algorithm?
Solution 1. a) The encrypted message for "HELLO" using the substitution cipher key given
would be "QBXXM".
b) Alice computes her public key as A=αamod p= 56mod 23 = 8. Bob computes his
public key as B=αbmod p= 515 mod 23 = 19. The shared secret key is K=Bamod p= 196
mod 23 = 2.
c) To encrypt the message using RSA encryption, compute c=memod n= 137mod 77 =
16. Therefore, the ciphertext produced is 16.
13 Cryptographic Algorithms and Protocols
Problem 1. Consider a secure communication protocol that uses Diffie-Hellman key exchange
to establish a shared secret key between Alice and Bob. If the prime modulus p= 23 and the base
g= 5, determine the shared secret key when Alice chooses a private key a= 6 and Bob chooses
a private key b= 15.
Solution 1. The shared secret key can be calculated by both Alice and Bob using the following
steps:
a) Alice calculates A=gamod p:
A= 56mod 23 = 25 mod 23 = 2
b) Bob calculates B=gbmod p:
B= 515 mod 23 = 30,517,578,125 mod 23 = 19
c) Alice and Bob share their calculated values Aand B, respectively.
d) Alice calculates the shared secret key: K=Bamod p:
K= 196mod 23 = 47,045,881 mod 23 = 2
e) Bob calculates the shared secret key: K=Abmod p:
K= 215 mod 23 = 32,768 mod 23 = 2
Thus, the shared secret key for both Alice and Bob is 2.
Problem 2. In the RSA encryption algorithm, suppose Alice chooses two prime numbers p= 11
and q= 17 for her public and private keys. She also chooses the public encryption exponent e= 7.
Determine the private decryption exponent d.
Solution 2. To find the private decryption exponent d, we must first calculate the following: -
n=p×q= 11 ×17 = 187 -φ(n)=(p−1) ×(q−1) = 10 ×16 = 160 - Then we solve the equation
e×d≡1 (mod φ(n)) for d:
7d≡1 (mod 160)
Solving this congruence equation, we find d= 23.
I’m happy to help with that. Here is a numerical problem on Cryptographic Algorithms and
Protocols for you:
14 16. PROBLEMS WITH END-TO-END ENCRYPTION SOLUTIONS
Problem 16. Consider a scenario where Alice wants to securely communicate with Bob using end-
to-end encryption. They decide to use the RSA cryptosystem for encryption and decryption. Alice’s
public key is (eA, NA) = (5,143), and her private key is (dA, NA) = (29,143). Bob generates his
own keys where his public key is (eB, NB) = (3,187), and his private key is (dB, NB) = (107,187).
a) If Alice wants to send a message M = 25 to Bob, what is the ciphertext that will be sent over
the network?
b) If Bob receives the ciphertext C = 97 from Alice, what is the original message M that Alice
intended to send him?
Solution 16.
a) To encrypt the message M = 25 using Alice’s public key, we use the encryption function:
C=MeAmod NA
C= 255mod 143
C= 3125 mod 143
C= 49
Therefore, the ciphertext that will be sent over the network is 49.
b) To decrypt the ciphertext C = 97 using Bob’s private key, we use the decryption function:
M=CdBmod NB
M= 97107 mod 187
M= 136904183893900215547781596700000000000000000000000000000000000000000000000000000000000000000 < /br > mod 187
M= 25
Therefore, the original message that Alice intended to send to Bob is 25.
15 17. CHALLENGES IN ACHIEVING SECURE AUTHENTICATION IN DISTRIBUTED SYS-
TEMS
Problem 17. Consider a distributed system where three entities need to authenticate each other
using a challenge-response protocol based on a shared secret key. Entity Agenerates a random
challenge cA= 347, Entity Bgenerates a random challenge cB= 512, and Entity Cgenerates a
random challenge cC= 635. The shared secret key between all entities is K= 123.
a) Entity Asends cAto Entity B, who responds with the result of cA⊕K. Calculate the response
sent by Entity Bto Entity A.
b) Entity Bsends cBto Entity C, who responds with the result of cB⊕K. Calculate the response
sent by Entity Cto Entity B.
c) Entity Csends cCto Entity A, who responds with the result of cC⊕K. Calculate the response
sent by Entity Ato Entity C.
Solution 17.
a) Entity Bcalculates the response as cA⊕K:
cA⊕K= 347 ⊕123 = 224
Therefore, Entity Bsends the response 224 to Entity A.
b) Entity Ccalculates the response as cB⊕K:
cB⊕K= 512 ⊕123 = 635
Therefore, Entity Csends the response 635 to Entity B.
c) Entity Acalculates the response as cC⊕K:
cC⊕K= 635 ⊕123 = 756
Therefore, Entity Asends the response 756 to Entity C.
16 Cryptographic Algorithms and Protocols
Problem: Alice wants to securely send a message to Bob using symmetric encryption. She
chooses the block cipher AES with a key size of 128 bits. The message she wants to send is 1280
bits long.
a) How many blocks will the message be divided into for encryption using AES?
b) If Alice and Bob are using the Electronic Code Book (ECB) mode, explain what kind of
vulnerability may arise in this scenario.
Solution:
a) The AES block size is 128 bits (16 bytes), so the 1280-bit message will need to be divided
into blocks of size 128 bits each.
Number of blocks = Message size / Block size = 1280 bits / 128 bits = 10 blocks
Therefore, the message will be divided into 10 blocks for encryption using AES.
b) In the ECB mode, each block of plaintext is encrypted separately with the same key. This
means that identical plaintext blocks will result in identical ciphertext blocks. This vulnerability can
be exploited by an attacker to detect patterns in the encrypted data, potentially revealing information
or relationships within the message. Additionally, ECB does not provide semantic security, so it
may leak information even if the plaintext is encrypted.
In the given scenario, if Alice sends any message that contains repeated blocks of plaintext
(e.g., patterns, images, or repeated phrases), an attacker can identify these repetitions and poten-
tially infer information about the message’s content.
I am unable to provide numerical problem questions and solutions for Cryptographic Algorithms
and Protocols at the moment. Would you like me to assist you with theoretical concepts or any other
form of assistance related to this topic?
I can certainly provide a problem and solution for you!
17 Cryptographic Algorithms and Protocols
Problem:
Consider the following scenario in a public-key encryption system using RSA:
Alice wants to send a confidential message to Bob. Bob has a public encryption key (e, n) =
(17,323) and a private key (d, n) = (275,323). Alice encrypts her message as follows: she repre-
sents the message as a number where each letter is assigned a value (A=1, B=2, ..., Z=26), and
then raises this number to the power of the public key (e)modulo nto obtain the ciphertext.
Alice’s message is "HELLO". The numerical representation of this message is [8, 5, 12, 12,
15]. Calculate the ciphertext that Alice will send to Bob.
Solution:
To find the ciphertext for the message "HELLO", we will encrypt each letter separately and
combine the results.
Let’s encode each letter:
H: 8 E: 5 L: 12 L: 12 O: 15
For letter "H": 817 ≡106 (mod 323)
For letter "E": 517 ≡9 (mod 323)
For letter "L": 1217 ≡144 (mod 323)
For the second "L": 1217 ≡144 (mod 323)
For letter "O": 1517 ≡21 (mod 323)
Now, combine these ciphertext values: 1069194144214421
Therefore, the ciphertext that Alice will send to Bob for the message "HELLO" is 10691941442144.
3 3. VULNERABILITIES IN ASYMMETRIC ENCRYPTION SCHEMES
Problem 3. Consider the RSA encryption scheme with public key (e, N) = (7,187). An attacker
intercepts a message m= 65 encrypted using this public key.
a) Compute the private key d.
b) Determine the decrypted message.
Solution 3.
a) To compute the private key d, we need to find the value such that ed ≡1 (mod φ(N)), where
φ(N)is Euler’s totient function.
Given that N= 187, we first need to calculate φ(N):
φ(N)=(p−1)(q−1) = 10 ×18 = 180.
Next, we solve for d:
7d≡1 (mod 180).
Solving this congruence, we get d= 103.
b) To decrypt the message, we calculate cd(mod N), where cis the intercepted ciphertext.
m= 65103 (mod 187).
Using fast modular exponentiation, we can simplify this calculation:
652≡52 (mod 187),
654≡522≡64 (mod 187),
658≡642≡141 (mod 187),
6516 ≡1412≡145 (mod 187),
6532 ≡1452≡79 (mod 187),
6564 ≡792≡77 (mod 187).
Therefore,
65103 ≡65 ×6532 ×6516 ×652×651
≡65 ×79 ×145 ×52
≡64 (mod 187).
Hence, the decrypted message is m= 64.
4 4. CRYPTANALYSIS OF SYMMETRIC KEY ALGORITHMS
Problem 4. Consider a block cipher with a block size of 64 bits and a key size of 128 bits. An
attacker performs a known-plaintext attack where they obtain 10 plaintext-ciphertext pairs. Each
pair has a plaintext of 64 bits and a corresponding ciphertext of 64 bits. The attacker wants to
determine the key using this information.
a) What is the maximum number of key candidates that the attacker needs to try to recover the
key using exhaustive search?
b) If the attacker has 2 plaintext-ciphertext pairs chosen by themselves (not obtained from
known plaintext) and wants to use a chosen-plaintext attack, how many queries do they need to
make to uniquely determine the key?
Solution 4.
a) Since the key size is 128 bits, the total number of possible keys is 2128. With the given 10
plaintext-ciphertext pairs, the attacker needs to try each key candidate against all pairs. Therefore,
the maximum number of key candidates to try is 2128 = 340,282,366,920,938,463,463,374,607,431,768,211,456.
b) In a chosen-plaintext attack, the attacker can choose their plaintexts. With 2 plaintext-
ciphertext pairs, each pair contributes 64 bits of information about the key (block size). Since
the key size is 128 bits, the attacker needs a total of 128/64 = 2 pairs to uniquely determine the
key. Therefore, the attacker needs to make a total of 2 queries.
I. Problem:
Consider a side-channel attack on a symmetric encryption algorithm that leaks information
about the encryption key based on the power consumption during encryption. Suppose you have
the following data:
- Power consumption when encrypting the plaintext 0x45: 100 units - Power consumption when
encrypting the plaintext 0xAF: 150 units
Assume that the power consumption is directly related to the number of bit changes in the
encryption key during encryption.
a) Determine the Hamming distance (number of differing bits) between the encryption keys
used for encrypting the plaintexts 0x45 and 0xAF.
b) If the encryption key consists of 8 bits, find the average power consumption when encrypting
a plaintext using this encryption algorithm.
Solution:
a) To find the Hamming distance between the encryption keys used for the two plaintexts:
0x45 =0100 0101
0xAF =1010 1111
The Hamming distance is the number of bit positions in which the two binary strings differ:
Hamming distance = 3 (bits that differ are in positions 2, 5, and 7)
b) With an 8-bit key, each bit change contributes to the power consumption. From part a, we
calculated three differing bits in the encryption key. Thus, the average power consumption when
encrypting a plaintext is:
Average power consumption =Total power consumption
Number of bit changes =100+150
3=250
3≈83.33 units
Therefore, the average power consumption when encrypting a plaintext using this encryption
algorithm is approximately 83.33 units.
5 6. LACK OF PROTECTION AGAINST QUANTUM COMPUTING THREATS
Problem 6. Consider the Shor’s algorithm for integer factorization. Given N= 15, find the
prime factors of Nusing Shor’s algorithm.
Solution 6. a) According to Shor’s algorithm, we need to find the period of the function f(x) =
axmod N, where a= 2.
Let’s find the period:
•f(0) = 20mod 15 = 1
•f(1) = 21mod 15 = 2
•f(2) = 22mod 15 = 4
•f(3) = 23mod 15 = 8
•f(4) = 24mod 15 = 1
The smallest period is r= 4. We need to find a1= 2(r/2) mod 15. Since r= 4,a1= 22
mod 15 = 4.
Next, we solve the equation gcd(ar/2±1, N). Either gcd(4 + 1,15) or gcd(4 −1,15).
•gcd(5,15) = 5 is a factor of N.
Therefore, the prime factors of N= 15 are 5and 3.
Thus, the prime factors of Nare 3and 5.
b) In this part, we find the same prime factors of N= 15 using the general approach. We
factorize 15 to prime numbers: 15 = 3 ×5.
c) Compare the results obtained from Shor’s algorithm and the general approach.
The results from Shor’s algorithm (3and 5) and the general approach (3and 5) are the same,
confirming the accuracy of both methods.
6 7. RISK OF COLLUSION ATTACKS ON CRYPTOGRAPHIC SYSTEMS
Problem 7. Consider a cryptographic system that uses a key exchange protocol with npartic-
ipants. Each participant holds a secret key that is randomly generated. If kparticipants collude to
share their secret keys, what is the probability that the colluding participants can decrypt a message
encrypted using the system?
Assume that the system is secure as long as at least one participant’s key remains secret.
Solution 7.
To find the probability that the colluding participants can decrypt the message, we need to
calculate the probability that all kparticipants’ keys are shared.
Let’s denote the total number of participants as nand the number of colluding participants as
k. The probability that all kparticipants’ keys are shared can be calculated as follows:
a) Probability that the first participant’s key is shared: k
n
b) Probability that the second participant’s key is shared given that the first participant’s key is
shared: k−1
n−1
c) Probability that the k-th participant’s key is shared given that the previous k−1participants’
keys are shared: k−(k−1)
n−(k−1) =1
n−(k−1)
Therefore, the overall probability that all kparticipants’ keys are shared is:
P(All kkeys are shared) = k
n×k−1
n−1×. . . ×1
n−(k−1)
Substitute n= 10 and k= 3 into the formula:
P(All 3keys are shared) = 3
10 ×2
9×1
8=1
120
Therefore, the probability that the colluding participants can decrypt the message is 1
120 .
7 8. INSECURE RANDOM NUMBER GENERATION IN CRYPTOGRAPHIC ALGORITHMS
Problem 8. Consider a scenario where a cryptographic algorithm requires generating random
numbers for secure key generation. However, the random number generator used is insecure and
produces predictable outputs.
Assume the insecure random number generator outputs a sequence of numbers as follows: 4,
8, 12, 16, 20, 24, ...
a) Calculate the next three numbers that will be generated by this insecure random number
generator.
b) Explain why using such an insecure random number generator for cryptographic purposes
is problematic.
Solution 8.
a) The pattern observed in the sequence of numbers generated by the insecure random number
generator is incrementing by 4. Therefore, the next three numbers that will be generated are: - 28
- 32 - 36
b) Using an insecure random number generator for cryptographic purposes is problematic be-
cause it introduces predictability in generating cryptographic keys or other sensitive parameters.
If an attacker can predict the numbers being used to generate cryptographic keys, they may be
able to break the encryption scheme and compromise the security of the system. Randomness is
a crucial element in cryptographic protocols to ensure secure communication and protect sensitive
information.
8 9. WEAKNESSES IN HASH FUNCTIONS
Problem 9. Consider a hash function H(x)=(ax +b) mod 11, where a= 3 and b= 5.
a) Calculate H(7).
b) Find an input xsuch that H(x)=6.
c) Determine whether the given hash function is collision-resistant.
Solution 9.
a) To find H(7), substitute x= 7 into the hash function:
H(7) = (3 ·7 + 5) mod 11 = 26 mod 11 = 4
Therefore, H(7) = 4.
b) To find an input xsuch that H(x)=6, set H(x)=6and solve for x:
(3x+ 5) mod 11 = 6
3x+ 5 = 6 ·11 + k, where 0≤k < 11
3x+ 5 = 66 + k
3x= 61 + k
Since kcan take values from 0 to 10, we check for ksuch that (61 + k)is divisible by 3:
k= 1
3x= 62
x=62
3= 202
3
Therefore, an input xsuch that H(x)=6is not an integer.
c) The given hash function is not collision-resistant because multiple inputs can map to the
same output. For example, H(0) = 5 and H(11) = 5, showing a collision.
9 Cryptographic Algorithms and Protocols
Problem 1. Consider a digital signature scheme that uses the RSA algorithm with a modulus
N= 187 and public exponent e= 13. Alice signs a message by raising it to the power of d= 37
(mod 187). If the original message is m= 45, what is the signature that Alice sends?
Solution 1. Given that N= 187,e= 13,d= 37, and m= 45, we can calculate the signature
as follows:
1. Calculate the public key component:
public key = (N, e) = (187,13)
2. Calculate the private key component: Firstly, we need to find pand qsuch that N=p·q= 187.
Through factorization, we find that p= 11 and q= 17. Next, calculate ϕ(N) = (p−1)(q−1) =
10 ·16 = 160. Then, calculate the private key d=e−1(mod ϕ(N)).
d= 13−1(mod 160) = 37
3. Calculate the signature: The signature is calculated as:
signature =md(mod N) = 4537 (mod 187)
signature = 148
Therefore, Alice will send the signature 148 for the message m= 45.
10 11. ISSUES WITH SECURE MULTIPARTY COMPUTATION PROTOCOLS
Problem 11. Consider a secure multiparty computation protocol involving three parties A,B,
and C. Each party has a secret number that they want to compute the sum of without revealing
their individual values. The protocol involves additive secret sharing where each party splits their
secret into two shares and sends one share to each of the other parties. The sum of the three
secret numbers should be computed by combining the shares in a secure manner.
Suppose A’s secret share sent to Bis 5, B’s secret share sent to Cis 3, and C’s secret share
sent to Ais 7.
a) Determine the sum of the three secret numbers without revealing the individual secrets.
b) Discuss any potential security risks or attacks that could compromise the secrecy of the
computed sum.
Solution 11.
a) To compute the sum of the three secret numbers, we can add up all the shares sent between
the parties:
A’s share sent to B(5) + B’s share sent to C(3) + C’s share sent to A(7)=5+3+7=15
Therefore, the sum of the three secret numbers is 15.
b) One potential security risk is collusion between two parties. If two parties collude and share
their secret shares, they can deduce the third secret share and thus compromise the secrecy of
the computed sum. In this case, if Aand Ccollude, they can add their secret shares to obtain B’s
secret share without Bknowing. This would reveal B’s secret and compromise the security of the
protocol.
10.1 12. DIFFICULTY IN ACHIEVING FORWARD SECRECY IN COMMUNICATION
PROTOCOLS
Problem 12. In a communication protocol, Alice and Bob agreed to use the Diffie-Hellman key
exchange algorithm to establish a shared secret key. Alice’s public key is g= 5 and p= 23. Bob’s
public key is g= 7 and p= 23. Given that the secret key (afor Alice and bfor Bob) is 6and 12
respectively, calculate the shared secret key.
Solution 12.
a) Alice calculates (gbmod p)amod pto obtain the shared secret key:
Alice: (76mod 23)12 mod 23
Calculating the values:
(279936 mod 23)12 mod 23
1412 mod 23
1,116,668,081,822,284 mod 23
21
Therefore, the shared secret key for Alice is 21.
b) Bob calculates (gamod p)bmod pto obtain the shared secret key:
Bob: (512 mod 23)6mod 23
Calculating the values:
(244140625 mod 23)6mod 23
186mod 23
34,992,033,553 mod 23
15
Therefore, the shared secret key for Bob is 15.
c) Since both Alice and Bob have calculated their respective shared secret keys, they can now
communicate securely using the Diffie-Hellman key exchange algorithm with a shared key of 15.
I. Problems on Cryptographic Algorithms and Protocols
11 13. CHALLENGES IN IMPLEMENTING HOMOMORPHIC ENCRYPTION
Problem 13. Consider a homomorphic encryption scheme where plaintexts are encoded as
integers mod 26. The encryption function takes a plaintext mand two random numbers r1and
r2to generate the ciphertext: c=m+r1mod 26 + r2mod 26. Suppose we want to perform a
homomorphic multiplication operation on two ciphertexts c1and c2, where c1= 10 and c2= 17.
Calculate the result of the homomorphic multiplication operation.
Solution 13. To perform homomorphic multiplication, we can simply multiply the ciphertexts:
cmul =c1×c2mod 26. Given c1= 10 and c2= 17, we have:
cmul = 10 ×17 mod 26 = 170 mod 26 = 12
Therefore, the result of the homomorphic multiplication operation on ciphertexts c1= 10 and
c2= 17 is cmul = 12.
This concludes the solution to the problem.
12 Cryptographic Algorithms and Protocols
Problem 1. Consider a simple substitution cipher where each letter of the alphabet is replaced
by a different letter. If we have encrypted the message "HELLO" using a substitution cipher and the
encryption key is as follows: {H→Q, E →B, L →X, O →M}, what is the encrypted message?
Problem 2. Alice and Bob want to establish a shared secret key using the Diffie-Hellman key
exchange protocol. If the prime number p= 23 and the primitive root α= 5, Alice chooses her
private key as a= 6 and Bob chooses his private key as b= 15, what is the shared secret key that
they will both compute?
Problem 3. In RSA encryption, if the public key is (n= 77, e = 7) and the message to be
encrypted is m= 13, what is the ciphertext produced using the RSA algorithm?
Solution 1. a) The encrypted message for "HELLO" using the substitution cipher key given
would be "QBXXM".
b) Alice computes her public key as A=αamod p= 56mod 23 = 8. Bob computes his
public key as B=αbmod p= 515 mod 23 = 19. The shared secret key is K=Bamod p= 196
mod 23 = 2.
c) To encrypt the message using RSA encryption, compute c=memod n= 137mod 77 =
16. Therefore, the ciphertext produced is 16.
13 Cryptographic Algorithms and Protocols
Problem 1. Consider a secure communication protocol that uses Diffie-Hellman key exchange
to establish a shared secret key between Alice and Bob. If the prime modulus p= 23 and the base
g= 5, determine the shared secret key when Alice chooses a private key a= 6 and Bob chooses
a private key b= 15.
Solution 1. The shared secret key can be calculated by both Alice and Bob using the following
steps:
a) Alice calculates A=gamod p:
A= 56mod 23 = 25 mod 23 = 2
b) Bob calculates B=gbmod p:
B= 515 mod 23 = 30,517,578,125 mod 23 = 19
c) Alice and Bob share their calculated values Aand B, respectively.
d) Alice calculates the shared secret key: K=Bamod p:
K= 196mod 23 = 47,045,881 mod 23 = 2
e) Bob calculates the shared secret key: K=Abmod p:
K= 215 mod 23 = 32,768 mod 23 = 2
Thus, the shared secret key for both Alice and Bob is 2.
Problem 2. In the RSA encryption algorithm, suppose Alice chooses two prime numbers p= 11
and q= 17 for her public and private keys. She also chooses the public encryption exponent e= 7.
Determine the private decryption exponent d.
Solution 2. To find the private decryption exponent d, we must first calculate the following: -
n=p×q= 11 ×17 = 187 -φ(n)=(p−1) ×(q−1) = 10 ×16 = 160 - Then we solve the equation
e×d≡1 (mod φ(n)) for d:
7d≡1 (mod 160)
Solving this congruence equation, we find d= 23.
I’m happy to help with that. Here is a numerical problem on Cryptographic Algorithms and
Protocols for you:
14 16. PROBLEMS WITH END-TO-END ENCRYPTION SOLUTIONS
Problem 16. Consider a scenario where Alice wants to securely communicate with Bob using end-
to-end encryption. They decide to use the RSA cryptosystem for encryption and decryption. Alice’s
public key is (eA, NA) = (5,143), and her private key is (dA, NA) = (29,143). Bob generates his
own keys where his public key is (eB, NB) = (3,187), and his private key is (dB, NB) = (107,187).
a) If Alice wants to send a message M = 25 to Bob, what is the ciphertext that will be sent over
the network?
b) If Bob receives the ciphertext C = 97 from Alice, what is the original message M that Alice
intended to send him?
Solution 16.
a) To encrypt the message M = 25 using Alice’s public key, we use the encryption function:
C=MeAmod NA
C= 255mod 143
C= 3125 mod 143
C= 49
Therefore, the ciphertext that will be sent over the network is 49.
b) To decrypt the ciphertext C = 97 using Bob’s private key, we use the decryption function:
M=CdBmod NB
M= 97107 mod 187
M= 136904183893900215547781596700000000000000000000000000000000000000000000000000000000000000000 < /br > mod 187
M= 25
Therefore, the original message that Alice intended to send to Bob is 25.
15 17. CHALLENGES IN ACHIEVING SECURE AUTHENTICATION IN DISTRIBUTED SYS-
TEMS
Problem 17. Consider a distributed system where three entities need to authenticate each other
using a challenge-response protocol based on a shared secret key. Entity Agenerates a random
challenge cA= 347, Entity Bgenerates a random challenge cB= 512, and Entity Cgenerates a
random challenge cC= 635. The shared secret key between all entities is K= 123.
a) Entity Asends cAto Entity B, who responds with the result of cA⊕K. Calculate the response
sent by Entity Bto Entity A.
b) Entity Bsends cBto Entity C, who responds with the result of cB⊕K. Calculate the response
sent by Entity Cto Entity B.
c) Entity Csends cCto Entity A, who responds with the result of cC⊕K. Calculate the response
sent by Entity Ato Entity C.
Solution 17.
a) Entity Bcalculates the response as cA⊕K:
cA⊕K= 347 ⊕123 = 224
Therefore, Entity Bsends the response 224 to Entity A.
b) Entity Ccalculates the response as cB⊕K:
cB⊕K= 512 ⊕123 = 635
Therefore, Entity Csends the response 635 to Entity B.
c) Entity Acalculates the response as cC⊕K:
cC⊕K= 635 ⊕123 = 756
Therefore, Entity Asends the response 756 to Entity C.
16 Cryptographic Algorithms and Protocols
Problem: Alice wants to securely send a message to Bob using symmetric encryption. She
chooses the block cipher AES with a key size of 128 bits. The message she wants to send is 1280
bits long.
a) How many blocks will the message be divided into for encryption using AES?
b) If Alice and Bob are using the Electronic Code Book (ECB) mode, explain what kind of
vulnerability may arise in this scenario.
Solution:
a) The AES block size is 128 bits (16 bytes), so the 1280-bit message will need to be divided
into blocks of size 128 bits each.
Number of blocks = Message size / Block size = 1280 bits / 128 bits = 10 blocks
Therefore, the message will be divided into 10 blocks for encryption using AES.
b) In the ECB mode, each block of plaintext is encrypted separately with the same key. This
means that identical plaintext blocks will result in identical ciphertext blocks. This vulnerability can
be exploited by an attacker to detect patterns in the encrypted data, potentially revealing information
or relationships within the message. Additionally, ECB does not provide semantic security, so it
may leak information even if the plaintext is encrypted.
In the given scenario, if Alice sends any message that contains repeated blocks of plaintext
(e.g., patterns, images, or repeated phrases), an attacker can identify these repetitions and poten-
tially infer information about the message’s content.
I am unable to provide numerical problem questions and solutions for Cryptographic Algorithms
and Protocols at the moment. Would you like me to assist you with theoretical concepts or any other
form of assistance related to this topic?
I can certainly provide a problem and solution for you!
17 Cryptographic Algorithms and Protocols
Problem:
Consider the following scenario in a public-key encryption system using RSA:
Alice wants to send a confidential message to Bob. Bob has a public encryption key (e, n) =
(17,323) and a private key (d, n) = (275,323). Alice encrypts her message as follows: she repre-
sents the message as a number where each letter is assigned a value (A=1, B=2, ..., Z=26), and
then raises this number to the power of the public key (e)modulo nto obtain the ciphertext.
Alice’s message is "HELLO". The numerical representation of this message is [8, 5, 12, 12,
15]. Calculate the ciphertext that Alice will send to Bob.
Solution:
To find the ciphertext for the message "HELLO", we will encrypt each letter separately and
combine the results.
Let’s encode each letter:
H: 8 E: 5 L: 12 L: 12 O: 15
For letter "H": 817 ≡106 (mod 323)
For letter "E": 517 ≡9 (mod 323)
For letter "L": 1217 ≡144 (mod 323)
For the second "L": 1217 ≡144 (mod 323)
For letter "O": 1517 ≡21 (mod 323)
Now, combine these ciphertext values: 1069194144214421
Therefore, the ciphertext that Alice will send to Bob for the message "HELLO" is 10691941442144.
3 3. VULNERABILITIES IN ASYMMETRIC ENCRYPTION SCHEMES
Problem 3. Consider the RSA encryption scheme with public key (e, N) = (7,187). An attacker
intercepts a message m= 65 encrypted using this public key.
a) Compute the private key d.
b) Determine the decrypted message.
Solution 3.
a) To compute the private key d, we need to find the value such that ed ≡1 (mod φ(N)), where
φ(N)is Euler’s totient function.
Given that N= 187, we first need to calculate φ(N):
φ(N)=(p−1)(q−1) = 10 ×18 = 180.
Next, we solve for d:
7d≡1 (mod 180).
Solving this congruence, we get d= 103.
b) To decrypt the message, we calculate cd(mod N), where cis the intercepted ciphertext.
m= 65103 (mod 187).
Using fast modular exponentiation, we can simplify this calculation:
652≡52 (mod 187),
654≡522≡64 (mod 187),
658≡642≡141 (mod 187),
6516 ≡1412≡145 (mod 187),
6532 ≡1452≡79 (mod 187),
6564 ≡792≡77 (mod 187).
Therefore,
65103 ≡65 ×6532 ×6516 ×652×651
≡65 ×79 ×145 ×52
≡64 (mod 187).
Hence, the decrypted message is m= 64.
4 4. CRYPTANALYSIS OF SYMMETRIC KEY ALGORITHMS
Problem 4. Consider a block cipher with a block size of 64 bits and a key size of 128 bits. An
attacker performs a known-plaintext attack where they obtain 10 plaintext-ciphertext pairs. Each
pair has a plaintext of 64 bits and a corresponding ciphertext of 64 bits. The attacker wants to
determine the key using this information.
a) What is the maximum number of key candidates that the attacker needs to try to recover the
key using exhaustive search?
b) If the attacker has 2 plaintext-ciphertext pairs chosen by themselves (not obtained from
known plaintext) and wants to use a chosen-plaintext attack, how many queries do they need to
make to uniquely determine the key?
Solution 4.
a) Since the key size is 128 bits, the total number of possible keys is 2128. With the given 10
plaintext-ciphertext pairs, the attacker needs to try each key candidate against all pairs. Therefore,
the maximum number of key candidates to try is 2128 = 340,282,366,920,938,463,463,374,607,431,768,211,456.
b) In a chosen-plaintext attack, the attacker can choose their plaintexts. With 2 plaintext-
ciphertext pairs, each pair contributes 64 bits of information about the key (block size). Since
the key size is 128 bits, the attacker needs a total of 128/64 = 2 pairs to uniquely determine the
key. Therefore, the attacker needs to make a total of 2 queries.
I. Problem:
Consider a side-channel attack on a symmetric encryption algorithm that leaks information
about the encryption key based on the power consumption during encryption. Suppose you have
the following data:
- Power consumption when encrypting the plaintext 0x45: 100 units - Power consumption when
encrypting the plaintext 0xAF: 150 units
Assume that the power consumption is directly related to the number of bit changes in the
encryption key during encryption.
a) Determine the Hamming distance (number of differing bits) between the encryption keys
used for encrypting the plaintexts 0x45 and 0xAF.
b) If the encryption key consists of 8 bits, find the average power consumption when encrypting
a plaintext using this encryption algorithm.
Solution:
a) To find the Hamming distance between the encryption keys used for the two plaintexts:
0x45 =0100 0101
0xAF =1010 1111
The Hamming distance is the number of bit positions in which the two binary strings differ:
Hamming distance = 3 (bits that differ are in positions 2, 5, and 7)
b) With an 8-bit key, each bit change contributes to the power consumption. From part a, we
calculated three differing bits in the encryption key. Thus, the average power consumption when
encrypting a plaintext is:
Average power consumption =Total power consumption
Number of bit changes =100+150
3=250
3≈83.33 units
Therefore, the average power consumption when encrypting a plaintext using this encryption
algorithm is approximately 83.33 units.
5 6. LACK OF PROTECTION AGAINST QUANTUM COMPUTING THREATS
Problem 6. Consider the Shor’s algorithm for integer factorization. Given N= 15, find the
prime factors of Nusing Shor’s algorithm.
Solution 6. a) According to Shor’s algorithm, we need to find the period of the function f(x) =
axmod N, where a= 2.
Let’s find the period:
•f(0) = 20mod 15 = 1
•f(1) = 21mod 15 = 2
•f(2) = 22mod 15 = 4
•f(3) = 23mod 15 = 8
•f(4) = 24mod 15 = 1
The smallest period is r= 4. We need to find a1= 2(r/2) mod 15. Since r= 4,a1= 22
mod 15 = 4.
Next, we solve the equation gcd(ar/2±1, N). Either gcd(4 + 1,15) or gcd(4 −1,15).
•gcd(5,15) = 5 is a factor of N.
Therefore, the prime factors of N= 15 are 5and 3.
Thus, the prime factors of Nare 3and 5.
b) In this part, we find the same prime factors of N= 15 using the general approach. We
factorize 15 to prime numbers: 15 = 3 ×5.
c) Compare the results obtained from Shor’s algorithm and the general approach.
The results from Shor’s algorithm (3and 5) and the general approach (3and 5) are the same,
confirming the accuracy of both methods.
6 7. RISK OF COLLUSION ATTACKS ON CRYPTOGRAPHIC SYSTEMS
Problem 7. Consider a cryptographic system that uses a key exchange protocol with npartic-
ipants. Each participant holds a secret key that is randomly generated. If kparticipants collude to
share their secret keys, what is the probability that the colluding participants can decrypt a message
encrypted using the system?
Assume that the system is secure as long as at least one participant’s key remains secret.
Solution 7.
To find the probability that the colluding participants can decrypt the message, we need to
calculate the probability that all kparticipants’ keys are shared.
Let’s denote the total number of participants as nand the number of colluding participants as
k. The probability that all kparticipants’ keys are shared can be calculated as follows:
a) Probability that the first participant’s key is shared: k
n
b) Probability that the second participant’s key is shared given that the first participant’s key is
shared: k−1
n−1
c) Probability that the k-th participant’s key is shared given that the previous k−1participants’
keys are shared: k−(k−1)
n−(k−1) =1
n−(k−1)
Therefore, the overall probability that all kparticipants’ keys are shared is:
P(All kkeys are shared) = k
n×k−1
n−1×. . . ×1
n−(k−1)
Substitute n= 10 and k= 3 into the formula:
P(All 3keys are shared) = 3
10 ×2
9×1
8=1
120
Therefore, the probability that the colluding participants can decrypt the message is 1
120 .
7 8. INSECURE RANDOM NUMBER GENERATION IN CRYPTOGRAPHIC ALGORITHMS
Problem 8. Consider a scenario where a cryptographic algorithm requires generating random
numbers for secure key generation. However, the random number generator used is insecure and
produces predictable outputs.
Assume the insecure random number generator outputs a sequence of numbers as follows: 4,
8, 12, 16, 20, 24, ...
a) Calculate the next three numbers that will be generated by this insecure random number
generator.
b) Explain why using such an insecure random number generator for cryptographic purposes
is problematic.
Solution 8.
a) The pattern observed in the sequence of numbers generated by the insecure random number
generator is incrementing by 4. Therefore, the next three numbers that will be generated are: - 28
- 32 - 36
b) Using an insecure random number generator for cryptographic purposes is problematic be-
cause it introduces predictability in generating cryptographic keys or other sensitive parameters.
If an attacker can predict the numbers being used to generate cryptographic keys, they may be
able to break the encryption scheme and compromise the security of the system. Randomness is
a crucial element in cryptographic protocols to ensure secure communication and protect sensitive
information.
8 9. WEAKNESSES IN HASH FUNCTIONS
Problem 9. Consider a hash function H(x)=(ax +b) mod 11, where a= 3 and b= 5.
a) Calculate H(7).
b) Find an input xsuch that H(x)=6.
c) Determine whether the given hash function is collision-resistant.
Solution 9.
a) To find H(7), substitute x= 7 into the hash function:
H(7) = (3 ·7 + 5) mod 11 = 26 mod 11 = 4
Therefore, H(7) = 4.
b) To find an input xsuch that H(x)=6, set H(x)=6and solve for x:
(3x+ 5) mod 11 = 6
3x+ 5 = 6 ·11 + k, where 0≤k < 11
3x+ 5 = 66 + k
3x= 61 + k
Since kcan take values from 0 to 10, we check for ksuch that (61 + k)is divisible by 3:
k= 1
3x= 62
x=62
3= 202
3
Therefore, an input xsuch that H(x)=6is not an integer.
c) The given hash function is not collision-resistant because multiple inputs can map to the
same output. For example, H(0) = 5 and H(11) = 5, showing a collision.
9 Cryptographic Algorithms and Protocols
Problem 1. Consider a digital signature scheme that uses the RSA algorithm with a modulus
N= 187 and public exponent e= 13. Alice signs a message by raising it to the power of d= 37
(mod 187). If the original message is m= 45, what is the signature that Alice sends?
Solution 1. Given that N= 187,e= 13,d= 37, and m= 45, we can calculate the signature
as follows:
1. Calculate the public key component:
public key = (N, e) = (187,13)
2. Calculate the private key component: Firstly, we need to find pand qsuch that N=p·q= 187.
Through factorization, we find that p= 11 and q= 17. Next, calculate ϕ(N) = (p−1)(q−1) =
10 ·16 = 160. Then, calculate the private key d=e−1(mod ϕ(N)).
d= 13−1(mod 160) = 37
3. Calculate the signature: The signature is calculated as:
signature =md(mod N) = 4537 (mod 187)
signature = 148
Therefore, Alice will send the signature 148 for the message m= 45.
10 11. ISSUES WITH SECURE MULTIPARTY COMPUTATION PROTOCOLS
Problem 11. Consider a secure multiparty computation protocol involving three parties A,B,
and C. Each party has a secret number that they want to compute the sum of without revealing
their individual values. The protocol involves additive secret sharing where each party splits their
secret into two shares and sends one share to each of the other parties. The sum of the three
secret numbers should be computed by combining the shares in a secure manner.
Suppose A’s secret share sent to Bis 5, B’s secret share sent to Cis 3, and C’s secret share
sent to Ais 7.
a) Determine the sum of the three secret numbers without revealing the individual secrets.
b) Discuss any potential security risks or attacks that could compromise the secrecy of the
computed sum.
Solution 11.
a) To compute the sum of the three secret numbers, we can add up all the shares sent between
the parties:
A’s share sent to B(5) + B’s share sent to C(3) + C’s share sent to A(7)=5+3+7=15
Therefore, the sum of the three secret numbers is 15.
b) One potential security risk is collusion between two parties. If two parties collude and share
their secret shares, they can deduce the third secret share and thus compromise the secrecy of
the computed sum. In this case, if Aand Ccollude, they can add their secret shares to obtain B’s
secret share without Bknowing. This would reveal B’s secret and compromise the security of the
protocol.
10.1 12. DIFFICULTY IN ACHIEVING FORWARD SECRECY IN COMMUNICATION
PROTOCOLS
Problem 12. In a communication protocol, Alice and Bob agreed to use the Diffie-Hellman key
exchange algorithm to establish a shared secret key. Alice’s public key is g= 5 and p= 23. Bob’s
public key is g= 7 and p= 23. Given that the secret key (afor Alice and bfor Bob) is 6and 12
respectively, calculate the shared secret key.
Solution 12.
a) Alice calculates (gbmod p)amod pto obtain the shared secret key:
Alice: (76mod 23)12 mod 23
Calculating the values:
(279936 mod 23)12 mod 23
1412 mod 23
1,116,668,081,822,284 mod 23
21
Therefore, the shared secret key for Alice is 21.
b) Bob calculates (gamod p)bmod pto obtain the shared secret key:
Bob: (512 mod 23)6mod 23
Calculating the values:
(244140625 mod 23)6mod 23
186mod 23
34,992,033,553 mod 23
15
Therefore, the shared secret key for Bob is 15.
c) Since both Alice and Bob have calculated their respective shared secret keys, they can now
communicate securely using the Diffie-Hellman key exchange algorithm with a shared key of 15.
I. Problems on Cryptographic Algorithms and Protocols
11 13. CHALLENGES IN IMPLEMENTING HOMOMORPHIC ENCRYPTION
Problem 13. Consider a homomorphic encryption scheme where plaintexts are encoded as
integers mod 26. The encryption function takes a plaintext mand two random numbers r1and
r2to generate the ciphertext: c=m+r1mod 26 + r2mod 26. Suppose we want to perform a
homomorphic multiplication operation on two ciphertexts c1and c2, where c1= 10 and c2= 17.
Calculate the result of the homomorphic multiplication operation.
Solution 13. To perform homomorphic multiplication, we can simply multiply the ciphertexts:
cmul =c1×c2mod 26. Given c1= 10 and c2= 17, we have:
cmul = 10 ×17 mod 26 = 170 mod 26 = 12
Therefore, the result of the homomorphic multiplication operation on ciphertexts c1= 10 and
c2= 17 is cmul = 12.
This concludes the solution to the problem.
12 Cryptographic Algorithms and Protocols
Problem 1. Consider a simple substitution cipher where each letter of the alphabet is replaced
by a different letter. If we have encrypted the message "HELLO" using a substitution cipher and the
encryption key is as follows: {H→Q, E →B, L →X, O →M}, what is the encrypted message?
Problem 2. Alice and Bob want to establish a shared secret key using the Diffie-Hellman key
exchange protocol. If the prime number p= 23 and the primitive root α= 5, Alice chooses her
private key as a= 6 and Bob chooses his private key as b= 15, what is the shared secret key that
they will both compute?
Problem 3. In RSA encryption, if the public key is (n= 77, e = 7) and the message to be
encrypted is m= 13, what is the ciphertext produced using the RSA algorithm?
Solution 1. a) The encrypted message for "HELLO" using the substitution cipher key given
would be "QBXXM".
b) Alice computes her public key as A=αamod p= 56mod 23 = 8. Bob computes his
public key as B=αbmod p= 515 mod 23 = 19. The shared secret key is K=Bamod p= 196
mod 23 = 2.
c) To encrypt the message using RSA encryption, compute c=memod n= 137mod 77 =
16. Therefore, the ciphertext produced is 16.
13 Cryptographic Algorithms and Protocols
Problem 1. Consider a secure communication protocol that uses Diffie-Hellman key exchange
to establish a shared secret key between Alice and Bob. If the prime modulus p= 23 and the base
g= 5, determine the shared secret key when Alice chooses a private key a= 6 and Bob chooses
a private key b= 15.
Solution 1. The shared secret key can be calculated by both Alice and Bob using the following
steps:
a) Alice calculates A=gamod p:
A= 56mod 23 = 25 mod 23 = 2
b) Bob calculates B=gbmod p:
B= 515 mod 23 = 30,517,578,125 mod 23 = 19
c) Alice and Bob share their calculated values Aand B, respectively.
d) Alice calculates the shared secret key: K=Bamod p:
K= 196mod 23 = 47,045,881 mod 23 = 2
e) Bob calculates the shared secret key: K=Abmod p:
K= 215 mod 23 = 32,768 mod 23 = 2
Thus, the shared secret key for both Alice and Bob is 2.
Problem 2. In the RSA encryption algorithm, suppose Alice chooses two prime numbers p= 11
and q= 17 for her public and private keys. She also chooses the public encryption exponent e= 7.
Determine the private decryption exponent d.
Solution 2. To find the private decryption exponent d, we must first calculate the following: -
n=p×q= 11 ×17 = 187 -φ(n)=(p−1) ×(q−1) = 10 ×16 = 160 - Then we solve the equation
e×d≡1 (mod φ(n)) for d:
7d≡1 (mod 160)
Solving this congruence equation, we find d= 23.
I’m happy to help with that. Here is a numerical problem on Cryptographic Algorithms and
Protocols for you:
14 16. PROBLEMS WITH END-TO-END ENCRYPTION SOLUTIONS
Problem 16. Consider a scenario where Alice wants to securely communicate with Bob using end-
to-end encryption. They decide to use the RSA cryptosystem for encryption and decryption. Alice’s
public key is (eA, NA) = (5,143), and her private key is (dA, NA) = (29,143). Bob generates his
own keys where his public key is (eB, NB) = (3,187), and his private key is (dB, NB) = (107,187).
a) If Alice wants to send a message M = 25 to Bob, what is the ciphertext that will be sent over
the network?
b) If Bob receives the ciphertext C = 97 from Alice, what is the original message M that Alice
intended to send him?
Solution 16.
a) To encrypt the message M = 25 using Alice’s public key, we use the encryption function:
C=MeAmod NA
C= 255mod 143
C= 3125 mod 143
C= 49
Therefore, the ciphertext that will be sent over the network is 49.
b) To decrypt the ciphertext C = 97 using Bob’s private key, we use the decryption function:
M=CdBmod NB
M= 97107 mod 187
M= 136904183893900215547781596700000000000000000000000000000000000000000000000000000000000000000 < /br > mod 187
M= 25
Therefore, the original message that Alice intended to send to Bob is 25.
15 17. CHALLENGES IN ACHIEVING SECURE AUTHENTICATION IN DISTRIBUTED SYS-
TEMS
Problem 17. Consider a distributed system where three entities need to authenticate each other
using a challenge-response protocol based on a shared secret key. Entity Agenerates a random
challenge cA= 347, Entity Bgenerates a random challenge cB= 512, and Entity Cgenerates a
random challenge cC= 635. The shared secret key between all entities is K= 123.
a) Entity Asends cAto Entity B, who responds with the result of cA⊕K. Calculate the response
sent by Entity Bto Entity A.
b) Entity Bsends cBto Entity C, who responds with the result of cB⊕K. Calculate the response
sent by Entity Cto Entity B.
c) Entity Csends cCto Entity A, who responds with the result of cC⊕K. Calculate the response
sent by Entity Ato Entity C.
Solution 17.
a) Entity Bcalculates the response as cA⊕K:
cA⊕K= 347 ⊕123 = 224
Therefore, Entity Bsends the response 224 to Entity A.
b) Entity Ccalculates the response as cB⊕K:
cB⊕K= 512 ⊕123 = 635
Therefore, Entity Csends the response 635 to Entity B.
c) Entity Acalculates the response as cC⊕K:
cC⊕K= 635 ⊕123 = 756
Therefore, Entity Asends the response 756 to Entity C.
16 Cryptographic Algorithms and Protocols
Problem: Alice wants to securely send a message to Bob using symmetric encryption. She
chooses the block cipher AES with a key size of 128 bits. The message she wants to send is 1280
bits long.
a) How many blocks will the message be divided into for encryption using AES?
b) If Alice and Bob are using the Electronic Code Book (ECB) mode, explain what kind of
vulnerability may arise in this scenario.
Solution:
a) The AES block size is 128 bits (16 bytes), so the 1280-bit message will need to be divided
into blocks of size 128 bits each.
Number of blocks = Message size / Block size = 1280 bits / 128 bits = 10 blocks
Therefore, the message will be divided into 10 blocks for encryption using AES.
b) In the ECB mode, each block of plaintext is encrypted separately with the same key. This
means that identical plaintext blocks will result in identical ciphertext blocks. This vulnerability can
be exploited by an attacker to detect patterns in the encrypted data, potentially revealing information
or relationships within the message. Additionally, ECB does not provide semantic security, so it
may leak information even if the plaintext is encrypted.
In the given scenario, if Alice sends any message that contains repeated blocks of plaintext
(e.g., patterns, images, or repeated phrases), an attacker can identify these repetitions and poten-
tially infer information about the message’s content.
I am unable to provide numerical problem questions and solutions for Cryptographic Algorithms
and Protocols at the moment. Would you like me to assist you with theoretical concepts or any other
form of assistance related to this topic?
I can certainly provide a problem and solution for you!
17 Cryptographic Algorithms and Protocols
Problem:
Consider the following scenario in a public-key encryption system using RSA:
Alice wants to send a confidential message to Bob. Bob has a public encryption key (e, n) =
(17,323) and a private key (d, n) = (275,323). Alice encrypts her message as follows: she repre-
sents the message as a number where each letter is assigned a value (A=1, B=2, ..., Z=26), and
then raises this number to the power of the public key (e)modulo nto obtain the ciphertext.
Alice’s message is "HELLO". The numerical representation of this message is [8, 5, 12, 12,
15]. Calculate the ciphertext that Alice will send to Bob.
Solution:
To find the ciphertext for the message "HELLO", we will encrypt each letter separately and
combine the results.
Let’s encode each letter:
H: 8 E: 5 L: 12 L: 12 O: 15
For letter "H": 817 ≡106 (mod 323)
For letter "E": 517 ≡9 (mod 323)
For letter "L": 1217 ≡144 (mod 323)
For the second "L": 1217 ≡144 (mod 323)
For letter "O": 1517 ≡21 (mod 323)
Now, combine these ciphertext values: 1069194144214421
Therefore, the ciphertext that Alice will send to Bob for the message "HELLO" is 10691941442144.
