Coursework 4

What is a one-way function and what are its properties?

A function is a one-way function, if is easy to compute for all but is hard (or infeasible) to compute.

What is a trapdoor one-way function? Give one example.

A trapdoor one-way function is a one-way function where given the it becomes feasible to compute but is infeasible otherwise. e.g. modular cube roots when we know and .

Use both Euclid’s algorithm and Extended Euclid’s algorithm to compute , showing all steps of the computations.

1Euclid(a, b):
2    if b == 0:
3        return a
4    else
5        return Euclid(b, a % b)

Extended Euclid’s (Unravelling):


Consider the primes and . Calculate and

For this we should know:

Explain which of the values or is usable as a public key for this given .

We have to choose an where and .

Let’s try first.

As we can see, . Let’s try just to show the difference.

As we can see, , therefore is NOT suitable. is suitable.

Use the Extended Euclid’s algorithm to calculate with the you have chosen.

We find our by finding the top value of in our previous table. We use the following rules (going backwards)

We get , therefore .

Encrypt and then decrypt the resulting ciphertext.

We use .


Using .

Consider the RSA algorithm with and .

  • Encipher the plaintext .

Use .

  • Break the cipher by finding , and .

We know:

  • ,

We can guess , as 2 primes.

To find , we know .

. We can use Extended-Euclid’s Algorithm.

We have , therefore .

Perform encryption and decryption using the RSA algorithm for the following:

, , ,

  1. Select such that and .
  2. Use Extended-Euclid’s algorithm to find .

Let’s try

, therefore is a good candidate. , therefore .


We know


We know

, , ,

  1. Select such that and .
  2. Use Extended-Euclid’s algorithm to find .

, therefore


We know:


We know:

Consider the RSA algorithm with , and .

Encipher the plaintext .

We know:

Decipher the resulting ciphertext to obtain again .

We know:

, therefore .


Why are these , and not really a good choice for RSA?

They are very small numbers which can be brute-forced quite quickly. Normally RSA will use numbers represented by 1024+ bits.

Consider a Diffie-Hellman key exchange with , , , . Compute and , and the secret key .

We know:

Therefore .

Consider a Diffie-Hellman scheme with , , , . Compute and , and the secret key .

We know:

Describe the man-in-the-middle attack to the Diffie-Hellman key exchange and how it could be prevented.

As Diffie-Hellman doesn’t provide authentication, any attacker, Charlie, could place themselves inbetween unsuspected agents, Alice and Bob. Charlie can complete the DH protocol with both Alice and Bob by intercepting their messages and establish a shared key for Alice and a separate shared key for Bob.

This attack can prevented by the use of digital signature schemes.

Describe the Diffie-Hellman key exchange protocol for three honest principals Alice, Bob and Carol. What would be the secret key for principals ?

  1. Alice, Bob and Carol all generate their random large private integer , , respectively and calculate their public integer .
  2. Each agent sends another agent’s public integer raised with their private key to another agent (in a circular chain).
  • Alice sends Carol’s public integer raised with her private integer () to Bob.
  • Bob sends Alice’s public integer raised with his private integer () to Carol.
  • Carol sends Bob’s public integer raised with her private integer () to Alice.
  1. Each agent calculates the shared key by raising what they receivied with their private integer.
  • Alice calculates .
  • Bob calculates .
  • Carol calculates .

Describe the El Gamal algorithm

El Gamal is a sped up version of DH where agent , can respond to with an encrypted message. In the following protocol:

  1. . calculates and sends it to $$B$.
  2. . calculates AND computes the shared key and uses it to encrypt a message .
  3. calculates to get the shared key .

Consider the El Gamal algorithm with , , , .

Consider the plaintext and let symmetric encryption be just the multiplication of the plaintext and the key (not a good encryption, of course, but that is not the point here).

Carry out the algorithm (for encryption).

Why are these , , , not adequate for El Gamal? Where is the problem? Would or be better?

They result in all of the keys being .

Explain in detail the main characteristics of cryptographic hash functions and give an example of an application.

The motivation behind hash functions is to create a fingerprint. A hash function, has the properties:

  • Compression: maps an input of arbitrary bit length to an output of fixed bit length .
  • Polynomial time computable.

A cryptographic hash function is additionally:

  • One-way (where given , it is hard to compute an where ).
  • And either:
  • 2nd-preimage resistant: it is computationally infeasile to find a second input that has the same output as any specified input.
  • Collision resistant: it is difficult to find two distinct inputs , where .

Explain in detail how Message Authentication Codes (MAC) work.

Bob and Alice both share a secret key . Alice uses a one-way hash function with parameter to hash a message to obtain a MAC. Alice sends this MAC along with her message to Bob who then attempts to calculate the same MAC with and in the one-way hash function. He compares his result with the MAC Alice sent and if they match, it’s valid. If they don’t, he cannot trust the message.

Explain in detail the main characteristics of a digital signature scheme. How can RSA be used for digital signatures?

Digital signatures take advantage of reversible public-key cryptosystems. A message can be encrypted with Alice’s private key; thus anyone with Alice’s public key (everyone) can decrypt the message, proving it was sent by Alice.