Guideline: You are allowed to use internet to search for the answers, however it is not allowed to work with other students to solve this assignment. Each individual should solve/search the answer himself/herself.

Reading Assignment: Read Section 5.2.2 Digital Signature using the Digital Signature Standard (DSS).

Q1) Prove that RSA works i.e. encryption using public key e followed by decryption using private key d always worked. In other words m^ed mod n = m

Hint:    a*) If p and q are prime, and n = pq, then  x^y mod n = x ^{( y mod (p-1)(q-1) )} mod n
            b*) Consider n > m

Ref*: C. Kaufman, R. Perlman, M. Speciner, Network Security, Private communication in a Public world, Prentice Hall, Englewood Cliffs, NJ, 1995.

The RSA algorithm works as follows:

1) Choose p and q prime numbers. Compute n = p*q.
2) Choose d at random such that d and (p-1)(q-1) are relatively prime. That means that their greatest common divisor is 1.
3) Generate e such that is the multiplicative inverse of d modulo (p-1)(q-1).
ed mod (p-1)(q-1) = 1

The following details the encryption and decryption steps. This example was taken from the book.

ENCRYPTION

C = ciphertext                                                            m = message                        0 < m < n

e and d was calculated in the example in the book: e = 413 and d = 53.

Equation (1): C = m^e mod n

Public key = (e, n) = (413, 629)                               m = 250, and n = p*q, in our case p= 17 and q=37

C = 250⁴¹³ mod 629 = 337

The ciphertext is 337 and can be trasmitted to the owner of the public key (413, 629)

DECRYPTION

Upon receiving the ciphertext, the private key is used to decrypt it:

Equation (2): m = C^d mod n

Private key = (d, n) = (53, 629)

m = 337⁵³ mod 629 = 250 and we get the message back that we started with.

Now let's take a look at the following equation:

m^ed mod n = m, we get this because decryption reverses the encryption and we get back the starting message.

From Equations (1) and (2) we have: m^e mod n = C and C^d mod n = m

Now raise both sides to power d, for decrypting the message and we get: ( m^e)^d mod n = C^d mod n

But as we can see from above Equation (2): C^d mod n = m

Therefore ( m^e)^d mod n = m or m^ed mod n = m.

Q2) Based on the proof in Q1, explain why n > m for RSA to work properly.

The RSA algorithm works with p and q primes, where n is the product of p and q. When encrypting a message M, this message M is turned into a number m < n (n=p*q), by using an agreend-upon reversible protocol, which means that the message is padded using a padding scheme. This will prevent and attacker to break the message.

Source:
http://en.wikipedia.org/wiki/RSA#Padding_schemes
http://en.wikipedia.org/wiki/Padding_%28cryptography%29

Q3) RSA is much slower than DES. However, unlike DES, RSA does not need a secrete key for each sender/receiver pair. On the other hand DES needs a secrete key for each sender/receiver pair, which needs to be conveyed to receiver by sender. Explain how we could use RSA and DES together such that we get the computational performance of DES and advantages of RSA.  Assume sender Alice, needs to send a large amount of data to receiver Bob.

DES is a symmetric-key cipher that uses a 56-bit key to encrypt a 64-bit block of plaintext. The sender and the receiver must agree on a shared key. Unfortunately, the weakness of DES is that anyone could potentially discover the shared key while transmitting it over the media. On the other hand DES is extremely fast in encrypting and decrypting the message.

RSA on the other hand requires that different keys – public and private keys – are used for encryption (public key) and decryption (private key). The public key is used to encrypt the message and the private key is used to decrypt the encrypted message. RSA is more secure since the public and private keys do not need to be transmitted to anyone. Also trying to break RSA is unfeasible since it would take a very very long time.

RSA and DES could be used together to get the performance of DES and the advantage of RSA. This means that RSA can be combined with DES to encrypt a messaged by means of an RSA digital envelope.

In the case when the sender Alice needs to send a large amount of data to receiver Bob, Alice will first encrypt the message with DES using a shared key. This shared key must be known by Bob in order to decrypt the message, thus it must be transmitted to Bob.

Next, Alice will find Bob's public key (RSA key) and it will use it to encrypt the DES shared key.

The DES encrypted message and the RSA-encrypted DES shared key together will form the RSA digital envelope. This will be sent to Bob.

Once Bob receives the RSA digital envelope, Bob will use his private key to decrypt the DES shared key, and then he will use the DES shared key to decrypt the message itself.

Q4) Write summary of DSS is your own words.

The DSS – Digital Signature Standard – includes the Digital Signature Algorithm. A digital signature is an electronically written signature. A digital signature consist of a private key and a public key. Each user will have a private key and a public key.

The public keys are known to everyone and the private key is known only to the user only. The private key is never shared with anyone.

A signature can only be generated by a user who has a private key. Anyone could verify a signature who has the public key. Therefore private keys are used in signature generation and public keys are used in the signature verification process. The DSA algorithm – so far is so perfect – that noone could break it and forge the signatures.

The DSA algorithm uses the following parameters: p, q, g are public keys and x and y are private keys.
q – is a prime number, 160 bit
p – is a prime number, and it must be either: 512, 576, 640, 704, 768, 832, 896, 960, 1024. q must be a factor of (p-1).
h – is a randomly selected integer between 1 and (p-1), such that h^(p-1)/q mod p > 1
g – is another integer and has the following value: g = h^(p-1)/q mod p
x – is an integer between 0 and q
k – is also an integer between 0 and q

The DSS requires to steps. The first step is to create the signature and the second step is to verify the signature.

Step 1: The Signature creation process

Let M be the "message". The signatures are the pair of number r and s. Then the following formulas hold and will generate the signatures:

r = (g^k mod p) mod q
s = (k^-1(SHA(M) + x*r)) mod q.

k^-1– is the multiplicative inverse of k mod q, that is (k*k^-1 ) mod q = 1

SHA(M) – is a 160 bit string output by the Secure Hash Algorithm
    
Step 2: The Signature verification process

In step 2, prior to verification, p, q, and g plus sender's public key and identity are made available to the verifier.

Let's say that the received versions are: M, r, s and y is the public key. The first check by the verifer will be very simple. If the following does not hold true than the signature will be rejected. So, both r and s must be between 0 and q. (If this is false, reject it.)

If this is true than the following equations must be verified:

w = (s)^-1 mod q
u1 = ( ( SHA(M) * w ) mod q
u2 = ( ( r*w ) mod q
v = ( ( (g)^u1 (y)^u2 ) mod p ) mod q

If v = r, then the signature is verified and the verifier can be certain that the received message was sent by the party holding the secret key x that corresponds to y.

Q5) Search for a large-integer factorization algorithm.

1. Explain the algorithm.
2. Write its pros and cons.
3. Perform its complexity analysis.

Hint: You could use internet, library or IEEE database to find an algorithm.

Large-integer factorization algorithms are devided into two categories: Special-purpose factoring algorithms, such as the Trial division, Pollard's rho and p-1 algorithms, Fermat's factorization method and so forth, and the General-purpose factoring algorithms, such as Dixon's algorithm, Quadratic sieve, General Number Field Sieve (GNFS) and Shor's algorithm for quantum computers just to name a few.

I picked the General Number Field Sieve (GNFS) algorithm since it is regarded as the best General-purpose factoring method for large integers. It has been said that the GNFS is the asymptotically fastest and by far the most complex factoring algorithm.

Explain the algorithm

The algorithm is based on the congruence of square method. The general number field sieve, requires a search for smooth numbers of order n^1/d, where d is some integer greater than one. The GNFS uses irreducible polynomials, rings, Guassian elimination and homomorphisms from the rings to get the two numbers x and y, with x² – y² divisible by n and finding the greatest common divisor of n and x – y.

Write its pros and cons
The GNFS is a very sophisticated and complex algorithm for factoring large-integer numbers. Even though it is complex, it does successfully factor a number over 100 digits relatively quickly.

Due to the setup steps necessary, the GNFS is significantly slower than other popular factoring methods for small numbers. It is exremely complex and

However, for large composite numbers the time spent in setting up the GNFS is negligible and the algorithm is dramatically faster than any other factoring algorithm.

Perform its complexity analysis

The complexity for factoring and integer n is:
 , for a constant c.