本文主要是介绍Cracking Public keys，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Public keys
I have generated public keys for each of you. You can download the public keys here: public-keys.tgz (hps:/umd.instructure.com/courses/1358965/files/78500682?wrap=1) (hps:/umd.instructure.com/courses/1358965/files/78500682/download?download_frd=1)
Inside this tarball, you will find a set of directories, one for each of you. To determine which one is yours, take the SHA-256 hash of your UID (with no whitespace and no newline at the end), and take the 5 least significant hex digits; that's your directory.
Within your directory, you will see 7 different RSA public keys, all stored in PEM format, ranging in sizes from 64 to 2048. Your goal is to determine what the private keys are.
For example, here is an example of a 128-bit private RSA key in PEM format:
Hmm, that's not very useful; to see what the actual values are from this, you can run this (assuming the name of the file is publickey.pem
At which point you would see this
As you can see, we learned two things: the modulus N and the exponent e. These are the two parts of the public key: N and e. Let's understand what these mean...
Background on RSA
-----BEGIN PUBLIC KEY----- MCwwDQYJKoZIhvcNAQEBBQADGwAwGAIRAPA7ineD+ahwXCDkjmk9uYUCAwEAAQ== -----END PUBLIC KEY-----
openssl rsa -pubin -in publickey.pem -text
RSA Public-Key: (128 bit) Modulus:
00:f0:3b:8a:77:83:f9:a8:70:5c:20:e4:8e:69:3d:
b9:85 Exponent: 65537 (0x10001)
RSA encrypon works through modular exponenaon (taking powers mod some number). To encrypt a message m, we raise m to the public exponent e mod the modulus N:
The modulus N is always the product of two large primes p and q. While N is made public, the precise values of p and q MUST remain private (we will see why in a moment). RSA is built on the belief that it is difficult to factor the product of two large primes. (If and when quantum computers become viable, factoring such large numbers will be easy, which will render RSA useless.)
In addion to this public exponent e, there is also a private exponent d; to decrypt a message, you just raise the ciphertext to that exponent mod the same modulus N:
Oen, e is some common fixed value (0x10001); it's d that is difficult to predict.
In a very real sense, e and d are "inverses" of one another, but only in the exponents of mod N.
In normal arithmec, if I have and I know e, then it is very easy to recover m; I just raise it to the power of . But in modular arithmec, you can't just compute inverses unless you know the modulus. Um, but don't you already know the modulus? I already said it's N.. well, not quite..
You see, a strange thing happens in modular arithmec. When operang over mod N, the exponents operate over a different modulus: they operate over mod , the Euler toent funcon. This has a rigorous definion, but for the sake of RSA moduli—which are always the products of two random primes p and q, the definion becomes very easy:
So, if you knew how to factor N, then you could easily calculate (p-1)(q-1), and once you know that P
There will be a git repository set up for you called extracredit ; for each key you crack, create a file called <keysize>.txt containing THREE lines:
1. p (the smaller of the two primes) 2. q (the larger of the two primes) 3. d (the private exponent)
and e, then you can easily compute
Cracking keys 5 Points
5/14/2024
Your task / what to submit: Crack the keys
Add Comment Your task is to compute these private exponents d for as many of the RSA public keys as you can.
ossible
For each of these values, provide it in hex format where each byte (two hex digits) are separated by a colon. For instance, the answer to the above public key should look like this, in a file called 128.txt
In addion to these .txt files, you must also submit all of the code that you used to crack the keys, as well as a file called Writeup.txt describing how you went about cracking them, in your own words.
Grading
You have to crack your keys; if you crack someone else's then you get no credit, so please be sure to check that you are working in the right directory!
Each key you crack will get you an extra point added to your final grade, up to a maximum of 5 points.
Addendum
In case you are curious, the corresponding private key PEM for the above public key is
To beer understand what is in this, you can run (assuming it's stored in a file called 128.pem ): openssl rsa -in 128.pem -text
这篇关于Cracking Public keys的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
