Suppose Alice wants to send some sensitive information (credit card numbers, SSNs, corporate secrets, health records, invasion orders to start a land war in Asia ) to Bob. To prevent eavesdroppers from being able to understand this communication if its intercepted, Alice can encrypt her original message (known as the plaintext) into a ciphertext. The ciphertext looks like gibberish to a casual eavesdropper. Upon receipt of the ciphertext, Bob can decrypt the message to recover the original plaintext.

There are two main categories of encryption algorithms: symmetric encryption (a.k.a. secret key encryption) and asymmetric encryption (a.k.a. public key encryption).

In symmetric encryption, Alice and Bob (the message sender and recipient, respectively) share a secret key that is used for both encrypting and decrypting the message. This key must be kept closely guarded if its compromised, an eavesdropper can use the key to understand all intercepted communications between Alice and Bob. This introduces some problems with key management. How should the secret key be securely shared between Alice and Bob initially? Also, how should the keys be securely updated once in use?

In asymmetric encryption, two different keys are used for encryption and decryption. To send a message to Bob, Alice encrypts the message with Bobs public key. The encrypted message can be decrypted only with Bobs corresponding private key. Just as its name implies, the public key is meant to be shared, meaning that anyone can encrypt a message. However, only someone with knowledge of the matching private key can decrypt the message. Bob does not share his private key with anyone (not even Alice).

RSA is a public key encryption system that remains widely used today. Its named after its inventors (Ronald Rivest, Adi Shamir, and Leonard Adleman), who first published a description of the algorithm in 1977. (A similar system was independently developed by English mathematician Clifford Cocks a few years prior while he was working for a UK intelligence agency, but it was not declassified until the late 1990s.) RSA consists of three main operations: 1) key generation, 2) encryption, and 3) decryption.

RSA Key Generation:

All communicating parties using RSA must have a public key (n, e) and a corresponding private key d. Heres how these numbers are chosen:

Pick two distinct prime numbers, p and q. In practice these must be very large numbers (hundreds of digits each) to ensure sufficient security.

Compute n = pq. Although n is shared as part of the public key, p and q must be kept secret.

Compute r = (p-1)(q-1).

Choose an integer e, 1 < e < r, such that e and r are relatively prime (i.e., gcd(e, r) = 1) .

Compute the integer d, which is the multiplicative inverse of e, mod r. In other words, (de) mod r = 1. (This is known as a modular inversion operation.)

RSA Encryption

To send a message to Bob, heres what Alice does:

Prepare a single integer plaintext M. If Alice wants to send information thats not an integer (like text characters), she can encode that information as an integer using some agreed-upon scheme. Using ASCII/Unicode would be a simple example of this.

Obtain Bobs public key (n, e).

Produce the ciphertext by computing C = M^e mod n. (This is known as a modular exponentiationoperation.)

Send the ciphertext C to Bob.

RSA Decryption

Upon receipt of the ciphertext C, heres what Bob does:

Use his private key d to compute C^d mod n (again, a modular exponentiation). It can be shown that this will result in the plaintext M.

Translate the integer M into the original message if necessary, by reversing the previously agreed-upon encoding scheme.

Security Analysis

RSA is (currently) considered secure due to the difficulty of factoring a large product of primes (the number n). Although the value of n is public, the values of its prime factors p and q are not. The person computing the private key knows both p and q, which allows him/her to easily compute r = (p-1)(q-1) and consequently the private key d. However, an attacker with knowledge of only the public key (n, e) has no known algorithm to efficiently compute d. Interestingly, no one has found any conclusive proof saying that an efficient algorithm for this cannot exist. If such an algorithm were developed, it would render RSA insecure. This would require a major overhaul of a lot of the security software being used today!

home / study / engineering / computer science / computer science questions and answers / need help with python lab assignment. need to create a program that does rsa operations. below ...

Question: Need help with Python lab assignment. Need to create a program that does RSA operations. Below is...

Need help with Python lab assignment. Need to create a program that does RSA operations. Below is all the background info:

As you can see from above, the RSA operations involve three main mathematical components:

Suppose Alice wants to send some sensitive information (credit card numbers, SSNs, corporate secrets, health records, invasion orders to start a land war in Asia ) to Bob. To prevent eavesdroppers from being able to understand this communication if its intercepted, Alice can encrypt her original message (known as the plaintext) into a ciphertext. The ciphertext looks like gibberish to a casual eavesdropper. Upon receipt of the ciphertext, Bob can decrypt the message to recover the original plaintext.

There are two main categories of encryption algorithms: symmetric encryption (a.k.a. secret key encryption) and asymmetric encryption (a.k.a. public key encryption).

In symmetric encryption, Alice and Bob (the message sender and recipient, respectively) share a secret keythat is used for both encrypting and decrypting the message. This key must be kept closely guarded if its compromised, an eavesdropper can use the key to understand all intercepted communications between Alice and Bob. This introduces some problems with key management. How should the secret key be securely shared between Alice and Bob initially? Also, how should the keys be securely updated once in use?

In asymmetric encryption, two different keys are used for encryption and decryption. To send a message to Bob, Alice encrypts the message with Bobs public key. The encrypted message can be decrypted only with Bobs corresponding private key. Just as its name implies, the public key is meant to be shared, meaning that anyone can encrypt a message. However, only someone with knowledge of the matching private key can decrypt the message. Bob does not share his private key with anyone (not even Alice).

RSA is a public key encryption system that remains widely used today. Its named after its inventors (Ronald Rivest, Adi Shamir, and Leonard Adleman), who first published a description of the algorithm in 1977. (A similar system was independently developed by English mathematician Clifford Cocks a few years prior while he was working for a UK intelligence agency, but it was not declassified until the late 1990s.) RSA consists of three main operations: 1) key generation, 2) encryption, and 3) decryption.

RSA Key Generation

All communicating parties using RSA must have a public key (n, e) and a corresponding private key d. Heres how these numbers are chosen:

Pick two distinct prime numbers, p and q. In practice these must be very large numbers (hundreds of digits each) to ensure sufficient security.

Compute n = pq. Although n is shared as part of the public key, p and q must be kept secret.

Compute r = (p-1)(q-1).

Choose an integer e, 1 < e < r, such that e and r are relatively prime (i.e., gcd(e, r) = 1) .

Compute the integer d, which is the multiplicative inverse of e, mod r. In other words, (de) mod r = 1. (This is known as a modular inversion operation.)

RSA Encryption

To send a message to Bob, heres what Alice does:

Prepare a single integer plaintext M. If Alice wants to send information thats not an integer (like text characters), she can encode that information as an integer using some agreed-upon scheme. Using ASCII/Unicode would be a simple example of this.

Obtain Bobs public key (n, e).

Produce the ciphertext by computing C = M^e mod n. (This is known as a modular exponentiationoperation.)

Send the ciphertext C to Bob.

RSA Decryption

Upon receipt of the ciphertext C, heres what Bob does:

Use his private key d to compute C^d mod n (again, a modular exponentiation). It can be shown that this will result in the plaintext M.

Translate the integer M into the original message if necessary, by reversing the previously agreed-upon encoding scheme.

Security Analysis

RSA is (currently) considered secure due to the difficulty of factoring a large product of primes (the number n). Although the value of n is public, the values of its prime factors p and q are not. The person computing the private key knows both p and q, which allows him/her to easily compute r = (p-1)(q-1) and consequently the private key d. However, an attacker with knowledge of only the public key (n, e) has no known algorithm to efficiently compute d. Interestingly, no one has found any conclusive proof saying that an efficient algorithm for this cannot exist. If such an algorithm were developed, it would render RSA insecure. This would require a major overhaul of a lot of the security software being used today!

Lab Assignment

As you can see from above, the RSA operations involve three main mathematical components:

Finding the greatest common divisor (gcd) of two numbers

Computing a modular inversion

Computing a modular exponentiation

(6 pts) Write a function gcd(a, b) that returns the greatest common divisor of the parameters a and b. You can use the Euclidean algorithm, which works by repeatedly computing remainders. Say you want to find the gcd of 1071 and 462:

First find the remainder when you divide the larger number (1071) by the smaller one (462): 1071 mod 462 = 147

Repeat with the previous smaller number (462) and the just-computed remainder (147): 462 mod 147 = 21

Repeat with the previous smaller number (147) and the just-computed remainder (21): 147 mod 21 = 0

Once the remainder becomes zero, the gcd is the smaller of the two numbers used to get that remainder. In this case, the gcd is 21.

(12 pts) Write a function modInv(a, b) that returns the multiplicative inverse of a, mod b (i.e., it should return a value x such that (ax) mod b = 1). You can use the extended Euclidean algorithm for this. In addition to computing the gcd of two numbers a and b, the extended algorithm returns the Bzout coefficients s and t. These are two integers that express the gcd as a linear combination of a and b: as + bt = gcd(a, b). Whena and b are relatively prime, the value of s turns out to be the multiplicative inverse of a, mod b (which is exactly what this function is looking for).

To run the extended Euclidean algorithm on two numbers a and b (assuming a > b), we keep track of four quantities that are repeatedly calculated: the remainder r_i, the quotient q_i, and the coefficients s_i and t_i.

First set some initial values: r₀ = a r₁ = b s₀ = 1 s₁ = 0 t₀ = 0 t₁ = 1

Then proceed as follows, starting at i = 1:

Compute q_i = r_i-1 / r_i (using integer division)

Compute r_i+1 = r_i-1 mod r_i

Compute s_i+1 = s_i-1 - q_is_i

Compute t_i+1 = t_i-1 - q_it_i

Repeat this set of calculations until the remainder becomes 0. The gcd is then the remainder from the previous round, and the Bzout coefficients are the s and t from the previous round.

The table below shows an example of running the extended Euclidean algorithm on a = 1073, b = 462. The shaded cells are the initial values; the algorithm starts running by computing q₁.

I	ri	si	ti	qi
0	1073	1	0
1	462	0	1	q1 = r0 / r1 = 1073 / 462 = 2
2	r2 = r0 mod r1 = 1073 mod 462 = 149	s2 = s0 - q1s1 = 1 - 2*0 = 1	t2 = t0 - q1t1 = 0 - 2*1 = -2	q2 = r1 / r2 = 462 / 149 = 3
3	r3 = r1 mod r2 = 462 mod 149 = 15	s3 = s1 - q2s2 = 0 - 3*1 = -3	t3 = t1 - q2t2 = 1 - 3*(-2) = 7	q3 = r2 / r3 = 149 / 15 = 9
4	r4 = r2 mod r3 = 149 mod 15 = 14	s4 = s2 - q3s3 = 1 - 9*(-3) = 28	t4 = t2 - q3t3 = -2 - 9*7 = -65	q4 = r3 / r4 = 15 / 14 = 1
5	r5 = r3 mod r4 = 15 mod 14 = 1	s5 = s3 - q4s4 = -3 - 1*28 = -31	t5 = t3 - q4t4 = 7 - 1*(-65) = 72	q5 = r4 / r5 = 14 / 1 = 14
6	r6 = r4 mod r5 = 14 mod 1 = 0

We stop as soon as we reach a remainder of 0 at r₆. Then the gcd is the remainder from the previous round, r₅ (which is 1, indicating 1073 and 462 are relatively prime). The two Bzout coefficients are the sand t from the previous round: s = -31 and t = 72. We can easily verify that as + bt = 1073*(-31) + 462*72 = 1, which matches the gcd of 1073 and 462.

Since a (1073) and b (462) are relatively prime, the value of s (-31) is the modular multiplicative inverse of a, mod b. We are working mod b, so we can add b to s to make it positive: -31 + 462 = 431. Thus, 431 is what the function should return. Verify: (1073*431) mod 462 = 462463 mod 462 = 1. Python tip: Use // for integer division; a single forward slash results in floating-point division.

6 pts) Write a function modExp(x, y, n) that computes and returns the value of x^y mod n. Use the fast modular exponentiation algorithm given in Figure 9.7.4 of your book.

(6 pts) Write a function generateRSAKeys(p, q) that returns the public key (n, e) and the private key d, given parameters for the two prime factors p and q. Your function can assume that the arguments will be primes. The function can find a value for e by starting at 3 and incrementing it by 2 until it finds a value where e is relatively prime to r that is, gcd(e, r) = 1. (Why does it make sense that even values for e need not be checked?) The return value can be a list of two elements containing one list (the public key) and one integer (the private key).

(6 pts) Write a program that uses all of your functions from above to carry out an RSA key generation, encryption, and decryption. Your program should get user input for two primes p and q, as well as a plaintext integer M. Display the RSA public and private keys that are generated. Show the ciphertext C that results from encrypting M using the public key. Finally, show the result from decrypting C using the private key. This decrypted output should match the original plaintext M. You can use the list of primes at http://primes.utm.edu/lists/small/1000.txt to help you test your program. Python tip: You can use the input() function like Javas Scanner class. By default, Python treats the entered information as a string, but you can call the int() function to convert it to an integer. Example: x = int(input("Enter an integer: ")) # x is now storing an int value print("You entered " + str(x))