You are given an RSA key pair (N , e) and d, and a unique encrypted message c.
You are required to get the decrypted message m. Implement task_1 to decrypt the message.
The formula to use for decryption is: m = c^d mod N.
The function task_1
accepts 3 string parameters that correlate to N
, d
, and c
, which are as follows:
N
is an encrypted value of the public keyd
is the encrypted private keyc
is the encrypted cipher string
The function task_1
works as follows:
-
Converts the 3 arguments (
n
,d
, andc
) to a base 16 integer. -
Using the power function, it calculates
c
to the power ofd
, modulusn
and setsm
equal to that value
- The function returns the hex value of
m
, with any trailing 'L' characters removed.
You are given a list of some of the most commonly-used passwords on the Internet. You are also given the SHA256 hash of a password randomly selected from this list.
Your job is to discover the plaintext password behind the hash.
The list of possible passwords has to be traversed, the password for comparison needs to be hashed and compared to the given hashed password.
Once the match is found, then the non-hashed version of the password is returned.
The function task_2
works as follows:
-
The list of common passwords is provided (as a list of strings, called
common_password_list
). -
Loop through each password string in the list
-
Convert the current password being compared (from the list) to the SHA256 hash version.
-
Check if the new hash password (
hashed_password
) matches the passed hash value (password_hash
).- If they are equal, then we know what the non-hashed version of the passed password is, which is stored as
password
. - If they are not equal, continue to the next value in the
common_password_list
.
- If they are equal, then we know what the non-hashed version of the passed password is, which is stored as
You’ve discovered a brand new cryptocurrency called kernelcoin (symbol: RTI).
You plan to start mining kernelcoin so that you can earn more. In order to do so, you need to create a valid block to append to the previous block.
A valid block contains the lowest nonce value that, when concatenated with the transaction string, and the hash of the previous block (in that order, i.e. nonce + transaction string + previous block hash), will produce a SHA256 hash with two leading zeros (the proof-of-work for this particular blockchain). Transaction strings have the syntax “UserID1: UserID2: X”, indicating that UserID1has transferred X kernelcoin to UserID2.
You are given all of these values, and your goal is to find the lowest possible nonce value for the resulting block.
The nonce value has to be incremented and tested as a part of the string that gets hashed in order to find the proof of work value.
If the proof of work (the first two characters of the hash, accessed using hash[:2]
) is not "00", then we know that the nonce value that was used was incorrect, and that we have to increment by 1 and retest.
We know that it is the lowest possible value because we are starting at 0 and continue to increase by 1, so as soon as the function hits the lowest possible correct value it will return that value.
The function task_3
works as follows:
-
The
nonce
integer is initialized to 0, the lowest possible nonce value that could be used. -
The
end_hash
string is set to the static "end" of the string. Since the only value that is to be changed throughout the function is thenonce
,end_hash
is initialized to a concatenation ofuser_id_1
, ":"user_id_2
, ":",str(amount)
, andprev_block_hash
. -
The
hash
string is initialized to theend_hash
string being combined with the initialnonce
value of 0, and then converted to SHA256. -
The function will loop through each nonce value, starting at zero, until the correct
nonce
is found, which at that point it will simply return that correct nonce value.nonce
is determined to be correct when the hash string that it is included in has "00" as the first two characters.
The algorithm you search for is dirt simple which makes it hard for attackers to traverse the entire key space with limited resources. Now, you’re given a unique RSA public key with a relatively small key size (6 4 bits).
Your goal is to get the private key.
At this point, we are given n
and e
, and we are expected to find d
, the private key.
We can find φ(N)
because φ(N) = (p−1)∗(q−1)
, and from there the formula to find d
is d = e^-1 mod φ(N)
. Therefore, we need to find the factors of n
, and then use that to find the modular inverse of n
and e
.
The modular inverse can be found using the Extended Euclidean Algorithm, which has pseudocode referenced here.
The function task_4
works as follows:
-
Both
n
ande
are converted from hex to int, to be used in calculations. -
The function
get_factors
is executed, and returns the value ofp
andq
, the two prime factors ofn
.-
The function utilizes Brent's Factorization Algorithm. Brent's Factorizaion Algorithm is a variation of Pollard Rho's Factorization method, where the calculation is more efficient, due to the detection of periodicity.
-
get_factors
also uses the functionintegral_power_of_2
in order to speed up the prime factorization algorithm. What this function does is detect if the index that is currently being checked is a power of 2. If so, then it sets x = y.
-
-
The function
get_private_key_from_p_q_e
is executed, and returns the value ofd
, the private key.-
get_private_key_from_p_q_e
uses the factorsp
andq
that were found usingget_factors
in Step 2, in order to calculate the private key.- We are able to calculate φ(N) (denoted as
phi
) by calculating(p−1) x (q−1)
. Once we have that value, the functionext_euclid
is used to find the modular multiplicative inverse using the Extended Euclidean Algorithm.
- We are able to calculate φ(N) (denoted as
-
-
The private key,
d
, is converted to hex (with trailing 'L' removed).
Read the paper “Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices”, which can be found at: https://factorable.net/weakkeys12.extended.pdf.
You are given a unique RSA public key, but the RNG (random number generator) used in the key generation suffers from a vulnerability described in the paper. In addition, you are given a list of public keys that were generated by the same RNG on the same system.
Your goal is to get the unique private key from your given public key using only the provided information.
Using the function get_private_key_from_p_q_e
from Task 4, the private key can be found.
The function task_5
works as follows:
-
Iterate through the entire length of the provided list
public_key_list
. -
Test each value. If the GCD of the given
n
and the value inpublic_key_list
has a GCD greater than 1, then we know that there is a factor that divides evenly into both. -
The value found in step 2 is assigned as the
p
value. We then divide that value into our originaln
in order to find the other factor,q
, using integer division to preserve accuracy. -
Then, the function
get_private_key_from_p_q_e
is used withp
,q
, andgiven_public_key_e
as inputs in order to return our desired private key,d
.
A message was encrypted with three different 1,024-bit RSA public keys, resulting in three different encrypted messages. All of them have the public exponent e = 3.
You are given the three pairs of public keys and associated encrypted messages. Your job is to recover the original message.
The function task_6
works as follows:
- The Chinese Remainder Theorem is used to find the value of c. Within
find_crt
, the Chinese Remainder Theorem uses the Extended Euclidean Algorithm in order to find the value ofbezout
.
bezout
is then used in the equation c_vals[i] * bezout * quotient
, which is computed for each c_
value, and then summed. After, the sum is then used to find the value of c
we are looking for by computing ans % product
.
-
Once we have our value of
c
, we need to take the cubed root ofc
in order to get m (from the equationc = m^3
). The cubed root is taken using a custom functionfind_root
that utilized binary sort, due to the large numbers used in RSA. -
The value of
m
returned from thefind_root
function is then converted and decoded in order to return the decrypted message.