代写密码学基础作业，涉及到RSA算法的理论和实践部分，以及最终的攻击部分。
Written Response Questions
Note: For written questions, please be sure to use complete, grammatically correct sentences where appropriate. You will be marked on the presentation and clarity of your answers as well as the content.
Variants of RSA
In RSA, the public key is a pair of integers (n, e), where n = pq for large primes p and q. The private key is the triple (p, q, d) where de ≡ 1 mod (p-1)(q-1). The encryption of a message m to yield the ciphertext c is c = m^e mod n and the decryption is m ≡ c^d mod n.
A key part of making RSA secure is to choose appropriate primes numbers. It is often stated that text-book RSA is weak because there are no restrictions on how to choose these primes. In this problem, we will investigate a variation of RSA that puts restrictions on the primes p and q.
Let us assume the genius security expert, Ensei Tankado, thinks that the following way of generating prime would be a good idea: choose the numbers g, b, and a such that p = 2ga+1 and q = 2gb+1 are prime. Ensei first puts an implicit restriction that the greatest common divisor of a and b is 1 (greatest common divisor of two integers is the largest integer that divides both the numbers).
He also adds the restriction that the term 2gab+a+b should be prime (in retrospect, this decision proves important for the security of the encryption scheme). Much like in text-book RSA, he then sets n = pq. During a round of beer, he boasts to his arch enemy Commander Trevor Strathmore that his scheme is secure (that it is impossible to factor n into primes p and q in polynomial time).
Mr. Strathmore never took this (or any security) course and blindly believes that Ensei has devised an “unbreakable” encryption scheme. To impress another security expert, Susan Fletcher, he gets involved in a bet with her that this scheme is unbreakable, even if given the values of a and b. Susan is intelligent, so after seeing the encryption scheme closely, she asks Trevor to give her any two values of a and b that fit the scheme. Blinded by incomplete knowledge, the commander gives Susan the values of a and b. We will see how Susan can factor n in time that is polynomial in the bit length of n and win the bet.
- Write the number n in terms of g, a and b.
- Use the above relation to give a closed formed expression for g.
- Write in one sentence, how the above information helps you in finding the factors of N .
The characters involved in this problem are taken from Dan Brown’s Digital Fortress.
TLS
Mallory sets up a Phishing website, steal the login information of CIBC customers. She lures a victim to her website with a Phishing email that contains a link to the website. During the TLS connection setup process, she has her server send the original CIBC certificate, which she retrieved earlier from the real CIBC website, to the victim’s browser. Will the browser notice the Phishing attack? Explain.
Mallory notices that the victim’s DNS server has not been patched against the severe vulnerability that led to a worldwide emergency upgrade of all DNS servers (see http://unixwiz.net/techtips/iguide-kaminsky-dns-vuln.html, not a required reading). She manages to execute a DNS cache poisoning attack. The victim’s host now maps to the IP address of a server controlled by Mallory. As before, the server will return the original CIBC certificate to a browser. Will the victim’s browser notice the Phishing attack when connecting? Explain.
When looking at the public verification key in the CIBC certificate, Mallory notices that it (and the private signing key) were generated on a machine affected by an OpenSSL vulnerability that made the machine’s “random” number generator and hence all generated keys predictable (see https://en.wikipedia.org/wiki/Random_number_generator_attack#Debian_OpenSSL, not a required reading). Mallory recomputes CIBC’s signing key and makes her server use it. (She also poisons the victim’s DNS cache, as explained earlier.) Will the victim’s browser notice the Phishing attack? Explain.
Even if the victim’s browser notices the Phishing attack in one of the scenarios above, why is the attacker still quite likely to succeed, at least with older versions of Firefox and Internet Explorer? (Assume that certificates are properly processed by a browser, i.e., software bugs is not a valid answer.)
GnuPG
A GnuPG public key is provided along with the assignment on the course website. Perform the following tasks. You can install GnuPG on your own computer, or use the version we have installed on the ugster machines.
Generate a GnuPG key pair for yourself. Use the RSA and RSA algorithm option, your real name, and an email address. Export this key using ASCII armor into a file called key.asc.
Note: older versions of GnuPG might not have the RSA and RSA algorithm option, so check that the version you are using has this option. The ugster machines have a new enough version, but the student.cs machine may not.Use this key to sign (not local-sign) the key. Its true fingerprint is: 7132 FAA5 D507 77DE 63B4 94A6 ADE8 4F18 A0F0 BCC9. Export your signed version of the p69liu key into a file called p69liu-signed.asc; be sure to use ASCII armor. [Note: signing a key is not the same operation as signing a message.]
Create a message containing your userid and name. Sign it using the key you generated, and encrypt it to the p69liu key. You should do both the encryption and signature in a single operation. Make sure to use ASCII armor, and save the output in a file called message.asc.
Briefly explain the importance of fingerprints in GnuPG. In particular, explain how users should check fingerprints and what type of attacks are possible if users do not follow this procedure properly.
Inference Attacks
The Human Resources department of FrobozzCo International has a table called Employee, with N records, in its database. This table stores the following information about each employee:
- Name: The employee’s first name, which is unique for every employee in the database.
- Birthdate: The employee’s year of birth.
- Occupation: The position the employee fills at the company. An employee with an occupation other than “Staff” is considered a specialist.
- Allegiance: The realm the employee swears their allegiance to. Although FrobozzCo is located in the land of Quendor, they believe that a diverse work force is beneficial to the production of magical products and employ workers from as far away as Antharia and Kovalli.
- Salary (in Zorkmids): the amount of hard-earned cash each employee takes home over the course of the year.
To deter employees from comparing their earnings and complaining about the amount of Zorkmids they take home to their families, the database is set up to suppress the Salary field in the output of queries. However, users can execute queries of the form
SELECT SUM(Salary) FROM Employee WHERE ...
- Use a tracker attack, as defined in class, to design a tracker and a set of three queries based on this tracker that will let you infer Lucille’s salary. Both the tracker and the three queries need to be of the form
SELECT SUM(Salary) FROM Employee ...
Assume that employees’ names are unique and not known to the attacker (apart from Lucille’s) and that the attacker has no additional information about Lucille (not even her status as a specialist). The only knowledge the attacker knows about the underlying distribution of the database is that FrobozzCo International hires an equal number of specialists (i.e. with an occupation other than “Staff”) and staff employees. In your solution, you should give 1) your tracker, and 2) the set of three queries.
Cornelius Flathead, the Human Resources Director of FrobozzCo International becomes aware of the tracker attack and forbids SUM(Salary) queries. Instead the Human Resources Department allows only queries of the form
SELECT COUNT(*) FROM Employee WHERE Q.
- Note that Q may include testing the value of the Salary field. (Again, queries that match fewer than k or more than
N - k, with the exception ofN, records are rejected.) How would you use queries of this type to learn Rachel’s salary? You may assume that no one in the database makes more than 200,000 Zorkmids and that all salaries are non-negative.