Public Key Cryptography and RSA 4. The purpose of this question is to implement

Question

Public Key Cryptography and RSA

4. The purpose of this question is to implement Sage functions for creating and verifying RSA signatures

a. Implement a Sage function that takes an integer and an RSA private key and produces an RSA signature of it.

b. Implement a Sage function that takes an RSA signature and a hash value and determines if the signature is valid.

c. Show your functions work by simulating a sign and verify. Show at least one sign and verify and also show an example that if the hash or signature are incorrect, your verify function correctly fails. (You may use the key generation function from an earlier problem).

Explanation / Answer

Encryption : Encryption means it is one common method of protecting information that is transmitted over unreliable links.

Example: Suppose for a message 'm' the encryption algorithm is 'Ek' and Decryption algorith 'Dk' using a key 'k' then the encryption algorithm must satisfy the following properties.

                                                 1. Dk(Ek(m)) =m

              2.Both Ek and Dk can be computed efficiently                            

                                             3. The security of the system depends only on the secrecy of the   key but does not depend on the secrecy of algorithms of E and D .

RSA signature : It is one of the first practical public-key cryptosystems which is used for secure data transmission. In such a cryptosystem, the encryption key is public and differs from the decryption key which is kept secret. In RSA, this asymmetry is based on the practical difficulty of factoring the product of two large prime numbers, the factoring problem etc.

a) Implement a Sage function that takes an integer and an RSA private key and produces an RSA signature of it.

#

# This is a function that performs RSA Signature

# N is an RSA modulus, and d is a private exponent.

# H is a Hash value to be signed, assumed to be a number less than

# and relatively prime to N

#

def RSA_sign(N, d, H):

    return RSA_decrypt(N, d, H)

b) Implement a Sage function that takes an RSA signature and a hash value and determines if the signature is valid.

#

# This is a function that performs RSA signature verification

# N is an RSA modulus, and e is a public exponent.

# H is a Hash value to be signed, assumed to be a number less than

# and relatively prime to N

# S is a signature of H

# Returns True if the signature S matches the Hash value H

#

def RSA_verify(N, e, H, S):

    return (H == RSA_encrypt(N, e, S))

C)     Show your functions work by simulating a sign and verify. Show at least one sign and verify and also show   an example that if the hash or signature are incorrect, your verify function correctly fails.

sage: (N, e, d) = RSA_key_generation(20)

sage: (N, e, d)

(544189, 162929, 162961)

sage: H = randint(1,N-1)

sage: H

236836

sage: S = RSA_sign(N, d, H)

sage: S

225401

sage: RSA_verify(N, e, H, S)

True

sage: H = randint(1,N-1)

sage: S = RSA_sign(N, d, H)

sage: RSA_verify(N, e, H, S)

True

sage: # now tweaking S will cause the verify to fail

sage: S = S - randint(1,1000)

sage: RSA_verify(N, e, H, S)

False

sage: # alternately tweaking H will cause the verify to fail

sage: H = randint(1,N-1)

sage: S = RSA_sign(N, d, H)

sage: H = H + randint(1,10000)

sage: RSA_verify(N, e, H, S)

False

.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.