CSIS 5857: Encoding and Encryption
Assignment 2: Public Key Encryption and Cipher Modes
Due Friday, March 17
These problems will give you experience different types of public key encryption, including RSA, Elgamal,
and Diffie-Hellman, as well as designing systems based on different types of cipher modes.
For these first three problems involving computation, you are required to show your work for full credit
(however, do feel free to use a calculator for the exponentiation, of course!)
1. In a public key system using RSA, suppose that you intercept a message sent to a user whose public key is
E = 7, n = 21.
a) What is the private key D of this user?
Hint: Think about how D was created. In particular, consider:
● What the primes p and q must have been.
● What the totient Φ must have been.
Ans.
To find the private key D, we need to find the two prime numbers p and q that were used to create the
public key n: 21
Below are the prime factors p, q of 21
[3, 7]
[3, 7]
totient Φ = (p-1) * (q-1) = (3-1) * (7-1) = 2 * 6 = 12
We need to find a value for D such that (E * D) mod Φ = 1
Which means, we need to find a value for D such that (7 * D) mod 12 = 1
try D = 1 | (7 * 1) mod 12 = 1 | 7 mod 12 != 1 | 7 != 1
try D = 2 | (7 * 2) mod 12 = 1 | 14 mod 12 != 1 | 2 != 1
try D = 3 | (7 * 3) mod 12 = 1 | 21 mod 12 != 1 | 9 != 1
try D = 4 | (7 * 4) mod 12 = 1 | 28 mod 12 != 1 | 4 != 1
try D = 5 | (7 * 5) mod 12 = 1 | 35 mod 12 != 1 | 11 != 1
try D = 6 | (7 * 6) mod 12 = 1 | 42 mod 12 != 1 | 6 != 1
try D = 7 | (7 * 7) mod 12 = 1 | 49 mod 12 = 1 | 1 = 1
So the private key is D = 7
b) Suppose the ciphertext you intercepted was the last digit of your Banner ID + 2 (for instance, if
your last digit is 9, you intercepted the ciphertext message 11).
What plaintext message M was sent?
Ans.
Banner ID: Y00856142
Ciphertext (2 + 2): 4
We can calculate the plaintext message M as follows:
M = (ciphertextᵖʳᶦᵛᵃᵗᵉ ᵏᵉʸ) mod n
M = (4⁷) mod 21
Decrypted plaintext message M = 4
2. Suppose that you are going to use Elgamal encryption to send me secure information, and that we have
agreed to use 19 as the prime and 3 as the primitive root generator. Also suppose that my public YA = 2.
Also suppose that you will choose the last digit of your Banner ID + 2 as your secret integer k (for
instance, if your last digit is 9, your k is 11).
a) What is your secret one time key K?
Ans.
Banner ID: Y00856142
Considering the last digit of the banner id 2, k = 2 + 2 = 4
K = YAᵏ mod p
K = 2⁴ mod 19
secret one time key, K = 16
b) Suppose that you were to use this value of K to encrypt the plaintext message 10. What is the
corresponding ciphertext?
Ans.
Encryption key = (Prime number (p), Primitive root (g) , YA)
Prime number (p) = 19
Primitive root (g) = 3
YA = 2
So, encryption key = ( 19, 3, 2 )
Plaintext = T = 10
Secret one time key (K) = 16
The ciphertext is expressed as a tuple ( c1, c2)
c1 = gᴷ mod p
c1 = 3¹⁶ mod 19 = 17
c2 = ( T x (YA)ᴷ ) mod p
c2 = ( 10 x 2¹⁶ ) mod 19 = 12
So, ciphertext = (c1, c2) = (17, 12).
3. Suppose that we are using Diffie-Hellman to create a secret shared key, using 71 as the prime p, and 7 as
the primitive root generator g.
Also suppose that you will choose the last digit of your Banner ID + 3 as your secret integer x (for
instance, if your last digit is 9, your x is 12).
a) Based on this, what number R1 would you send to me?
Ans.
Compute secret integer x, by adding 3 to last digit of Banner ID: Y00856142
x=2+3=5
we can compute your public value R1 using the formula R1 = gˣ mod p where
g = primitive root generator
p = prime
x = secret integer
R1 = 7⁵ mod 71
R1 = 51
b) Supposed that you received the number 54 from me as my number R2. What would you then
compute for our shared key k?
Ans.
We can compute the shared key k using the formula k = R2ˣ mod p
where x is secret integer
p is prime
Shared key k = 54⁵ mod 71
Shared key k = 1
4. Unfortunately, Barney Fife is still in charge of your information security. He wants to use RSA public key
encryption to securely send credit card numbers from multiple locations to a central server. For this
problem, assume all credit card numbers are 16 digits long.
Specifically, he would use RSA to encrypt a credit card number using the public key of the server, and then
send that encrypted number to the server.
You must assume that the server public key is well known, and that the encrypted message is being sent
over an unsecured network (and may therefore be viewed by Darth).
a) Why is this a bad idea? Specifically, if Darth intercepts the encrypted credit card number, how could
he quickly determine the plaintext credit card number that it corresponds to?
Ans.
We do not recommend sending credit card numbers over unsecured networks using RSA public
key cryptography. RSA ciphers are vulnerable to attacks known as "brute force" or "complement search"
attacks.
In a brute force attack, the attacker tries all possible keys until he finds a good one that can
decrypt the message. If Darth intercepted an encrypted credit card number, he could potentially brute
force all possible private keys until he found one that could decrypt the message. Once you find the
proper private key, you can identify a regular credit card number.
The strength of RSA encryption depends on the key size used. The larger the key size, the
exponentially more difficult it is to perform a brute force attack. However, even with very long key
lengths, an attacker with sufficient resources can brute force and discover shared credit card numbers.
Therefore, we do not recommend using RSA public key encryption to transmit sensitive
information over unsecured networks. Instead, more secure methods such as symmetric encryption or
secure exchange protocols should be used.
b) What is a simple way that you could have Barney modify this process so that he could still use RSA
to send 16-digit credit card numbers, but to keep them secure from the kind of attack in part a)?
Ans.
To protect the 16-digit credit card number from brute force attacks, Barney was able to use a
technique called padding. Padding adds random data to the plaintext of the message before encryption,
making it more difficult for an attacker to determine the original message.
In this case, Barney can append random data to his 16-digit credit card number before encrypting it with
the server's public key. The padding can be of any length as long as it is long enough to make brute force
attacks impossible. When the server receives the encrypted credit card number, it uses the private key to
decrypt it and remove the padding to reveal the original his 16 digit credit card number.
Padding schemes such as PKCS#1 v1.5 and OAEP (Optimal Asymmetric Encryption Padding)
can be used to ensure encryption security. These padding schemes are standardized and undergo
rigorous testing to ensure their safety.
5. You are working for a company that provides security recommendations for a number of IT firms, each
with different requirements and goals.
For each of the following scenarios, give the transmission mode you would recommend or sending
information, and why you would do so.
a) Company A sends messages in blocks (that is, no streaming). These messages are very large,
containing many repeated blocks. Speed of encryption/decryption is not a concern. They are willing
to generate and send a new key for each message if necessary.
b) Company B streams messages over a network. They are willing to generate and exchange a new key
each time. To save time during encryption, they would like to have the ability to generate the entire
key stream in advance (that is, before the actual message to be encrypted is known).
c) Company C sends data from one site to another burned as files onto CD-ROM disks (rather than
sending it over a network). Many of these files contain similar data. They still want to make sure that
data remains as secure as possible even if someone else intercepts the shipments.
d) Company D sends message in blocks (that is, no streaming). These messages are very short,
consisting of few blocks, and are not sent very often. They also have parallel hardware that they
would like to take advantage of in order to speed up the encryption/decryption process. They would
like to avoid having to generate and exchange new keys for each message.
e) Company E streams messages over a network. These messages are generally long and sent very
often. They will not generate new keys for each message.
Ans.
For Company A, we recommend using a block encryption algorithm such as AES (Advanced
Encryption Standard) or Blowfish. These algorithms are designed for block-based encryption and can
efficiently encrypt and decrypt large messages with repeated blocks. Keys are securely exchanged
between parties using a secure key exchange protocol such as Diffie-Hellman or RSA, as the company is
willing to generate and send a new key for every message will do so. is recommended.
For Company B, we recommend using a stream cipher encryption algorithm such as RC4 or
Salsa20. These algorithms are designed for streaming encryption and allow you to pre-generate the
entire key stream, enabling fast message encryption. Organizations are willing to generate and exchange
new keys each time, so they should use a secure key exchange protocol such as Diffie-Hellman or RSA
to ensure that keys are exchanged securely between parties. It is recommended. gain.
Company C recommends encrypting your data using a strong encryption algorithm such as AES
or Blowfish before writing it to CD-ROM. We also recommend that you generate a hash of your data
using a secure hash function such as SHA-256 or SHA-3 and include it in your encrypted data. This
means that any manipulation of your data will be detected, keeping your data as safe as possible even if
your shipment is intercepted.
Company D recommends using block cipher algorithms such as AES and Blowfish and parallel
processing algorithms such as AES-NI and AES-GCM-SIV. These algorithms can use parallel hardware
to speed up the encryption and decryption process. The company wants to avoid generating and
exchanging new keys for each message, so it uses a secure key derivation function such as HKDF
(HMAC-based key derivation function) to create a single master key. Extract the key from We
recommend that you derive multiple keys. some news.
For Company E, we recommend that you encrypt your messages using a stream cipher
encryption algorithm such as RC4 or Salsa20. Because messages are generally long and sent frequently,
stream encryption allows fast encryption and decryption of messages. Since your company does not
generate new keys for every message, use a secure key exchange protocol such as Diffie-Hellman or
RSA to ensure that keys are exchanged securely between parties. is recommended. We also recommend
that you change your keys regularly to avoid compromising them over time.
Additional problems for Graduate Students:
6. Suppose that you are using CBC mode to send a message that consists of n blocks.
Furthermore, suppose that there is a transmission error in sending ciphertext block i to the recipient.
Specifically, a single bit is changed due to noise (for example, a 1 in the ciphertext sent is changed to a 0 in
the ciphertext received).
Clearly, this will lead to an error in the plaintext block i that the recipient creates during decryption. How
many other blocks will also be affected?
Ans.
In CBC mode, each block of plaintext is XORed with the previous block of ciphertext before encryption.
Therefore, if the transmission of ciphertext block i fails, the decryption process also fails plaintext block i.
Also, this error is propagated to the next plaintext block due to XOR with the wrong ciphertext block.
The error continues until the end of the message is reached. Therefore, a single-bit error in a ciphertext
block in CBC mode affects the corresponding plaintext block and all subsequent plaintext blocks.
In summary, if there is a transmission error in ciphertext block i in CBC mode, the error affects the ith
plaintext block and all subsequent plaintext blocks.
7. This question will involve adding two points on the elliptic curve E13(1, 1) – in other words, the elliptic
curve y2 = x3 + x + 1 (that is, the one I used in my notes).
The first point is (11, 2).
The second point depends on the last digit of your Banner ID:
Last digit Point to add
0 (0, 12)
1 (1, 4)
2 (1, 9)
3 (4, 11)
4 (5, 1)
5 (5, 12)
6 (7, 0)
7 (8, 1)
8 (8, 12)
9 (10, 7)
For example, if the last digit of your Banner ID was 3, you would compute the sum (11, 2) + (4, 11).
You must also show your work to receive full credit on this problem.
Ans.
Banner ID: Y00856142
last digit: 2
elliptic curve: y² = x³ + x + 1 mod 13
Add two points (11, 2) and (1, 9)
First, we need to find slope of these two points
slope = (y2-y1)/(x2-x1) mod 13
slope = (9-2)/(1-11) mod 13
slope = 63
By using slope, we can find x3 and y3 (sum of point1 and point2)
x3 = (slope² - x1 - x2) mod 13
x3 = ( (63)² - 11 - 1 ) mod 13
x3 = 5
y3 = (-slope * (x3 - x1) - y1) mod 13
y3 = (-(63) * (5 - 11) - 2) mod 13
y3 = 12
We need to make sure that result (5, 12) is a point on elliptic curve
lhs = y² mod 13
lhs = 12² mod 13
lhs = 1
rhs = x³ + x + 1 mod 13
rhs = 5³ + 5 + 1 mod 13
rhs = 1
Point (5, 12) is present on elliptic curve y² = x³ + x + 1
So, Sum of points: (11, 2) + (1, 9) = (5, 12)
