This is the first set of number-theoretic cryptography challenges, and also our coverage of message authentication.
This set is significantly harder than the last set. The concepts are new, the attacks bear no resemblance to those of the previous sets, and... math.
On the other hand, our favorite cryptanalytic attack ever is in this set (you'll see it soon). We're happy with this set. Don't wimp out here. You're almost done!
from collections import defaultdict
from random import randint, randbytes, choice
# From pyca/cryptography
from cryptography.hazmat.primitives import padding
from cryptography.hazmat.primitives.ciphers import Cipher, algorithms, modes
from cryptography.hazmat.primitives.hashes import Hash, SHA1, SHA256
from cryptography.hazmat.primitives.hmac import HMAC
def pad_pkcs7(text):
padder = padding.PKCS7(128).padder()
return padder.update(text) + padder.finalize()
def unpad_pkcs7(text):
unpadder = padding.PKCS7(128).unpadder()
return unpadder.update(text) + unpadder.finalize()
def aes_128_cbc_encrypt(ptext, key, iv):
encryptor = Cipher(algorithms.AES128(key), modes.CBC(iv)).encryptor()
return encryptor.update(pad_pkcs7(ptext)) + encryptor.finalize()
def aes_128_cbc_decrypt(ctext, key, iv):
decryptor = Cipher(algorithms.AES128(key), modes.CBC(iv)).decryptor()
return unpad_pkcs7(decryptor.update(ctext) + decryptor.finalize())
def sha1(message):
h = Hash(SHA1())
h.update(message)
return h.finalize()
def sha256(message):
h = Hash(SHA256())
h.update(message)
return h.finalize()
def hmac_sha256(key, message):
h = HMAC(key, SHA256())
h.update(message)
return h.finalize()
def modexp(a, e, n):
# Compute (a**e)%n where e may be very large
r = 1
p = a
while e > 0:
if e%2 == 1:
r = (r*p)%n
p = (p*p)%n
e >>= 1
return r
def modinv(a, n):
# Inverse of a modulo n (extended Euclidean algorithm)
t, new_t = 0, 1
r, new_r = n, a
while new_r != 0:
q = r//new_r
t, new_t = new_t, t-q*new_t
r, new_r = new_r, r-q*new_r
if r > 1:
raise ZeroDivisionError("no modular inverse")
if t < 0:
t += n
return t
def i2b(n):
# Integer to bytes
num_bytes = 1
while True:
try:
return n.to_bytes(num_bytes, "big")
except OverflowError:
num_bytes += 1
def b2i(b):
# Bytes to integer
return int.from_bytes(b, "big")
For one of the most important algorithms in cryptography this exercise couldn't be a whole lot easier.
Set a variable "p" to 37 and "g" to 5. This algorithm is so easy I'm not even going to explain it. Just do what I do.
Generate "a", a random number mod 37. Now generate "A", which is "g" raised to the "a" power mod 37 --- A = (g**a) % p.
Do the same for "b" and "B".
"A" and "B" are public keys. Generate a session key with them; set "s" to "B" raised to the "a" power mod 37 --- s = (B**a) % p.
Do the same with A**b, check that you come up with the same "s".
To turn "s" into a key, you can just hash it to create 128 bits of key material (or SHA256 it to create a key for encrypting and a key for a MAC).
Ok, that was fun, now repeat the exercise with bignums like in the real world. Here are parameters NIST likes:
p:
ffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024
e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd
3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec
6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5ae9f
24117c4b1fe649286651ece45b3dc2007cb8a163bf0598da48361
c55d39a69163fa8fd24cf5f83655d23dca3ad961c62f356208552
bb9ed529077096966d670c354e4abc9804f1746c08ca237327fff
fffffffffffff
g: 2
This is very easy to do in Python or Ruby or other high-level languages that auto-promote fixnums to bignums, but it isn't "hard" anywhere.
Note that you'll need to write your own modexp (this is blackboard math, don't freak out), because you'll blow out your bignum library raising "a" to the 1024-bit-numberth power. You can find modexp routines on Rosetta Code for most languages.
The 1,536-bit prime p and generator value g = 2 are among the various values recommended in RFC 3526. There does not seem to be a required size for the private key, but 256 bits appears as a recommendation in a few places. That the session keys as generated by A and B are equal just follows from the law of exponents: $s = B^a = (g^b)^a = (g^a)^b = A^b$.
P = int(
"ffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024"
"e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd"
"3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec"
"6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5ae9f"
"24117c4b1fe649286651ece45b3dc2007cb8a163bf0598da48361"
"c55d39a69163fa8fd24cf5f83655d23dca3ad961c62f356208552"
"bb9ed529077096966d670c354e4abc9804f1746c08ca237327fff"
"fffffffffffff",
16
)
G = 2
def generate_dh_keypair(prime, generator):
# Return private key, public key
k = randint(2**255, 2**256-1)
K = modexp(generator, k, prime)
return k, K
def key_value_to_bytes(s):
return sha1(i2b(s))[:16]
def session_key(private_key, public_key, prime):
# My private key, their public key
return key_value_to_bytes(modexp(public_key, private_key, prime))
a, A = generate_dh_keypair(P, G)
b, B = generate_dh_keypair(P, G)
session_key(a, B, P) == session_key(b, A, P)
True
Use the code you just worked out to build a protocol and an "echo" bot. You don't actually have to do the network part of this if you don't want; just simulate that. The protocol is:
A->B
Send "p", "g", "A"
B->A
Send "B"
A->B
Send AES-CBC(SHA1(s)[0:16], iv=random(16), msg) + iv
B->A
Send AES-CBC(SHA1(s)[0:16], iv=random(16), A's msg) + iv
(In other words, derive an AES key from DH with SHA1, use it in both directions, and do CBC with random IVs appended or prepended to the message.)
Now implement the following MITM attack:
A->M
Send "p", "g", "A"
M->B
Send "p", "g", "p"
B->M
Send "B"
M->A
Send "p"
A->M
Send AES-CBC(SHA1(s)[0:16], iv=random(16), msg) + iv
M->B
Relay that to B
B->M
Send AES-CBC(SHA1(s)[0:16], iv=random(16), A's msg) + iv
M->A
Relay that to A
M should be able to decrypt the messages. "A" and "B" in the protocol --- the public keys, over the wire --- have been swapped out with "p". Do the DH math on this quickly to see what that does to the predictability of the key.
Decrypt the messages from M's vantage point as they go by.
Note that you don't actually have to inject bogus parameters to make this attack work; you could just generate Ma, MA, Mb, and MB as valid DH parameters to do a generic MITM attack. But do the parameter injection attack; it's going to come up again.
class Person:
def __init__(self, name):
self.name = name
self.name_bytes = bytes(name, encoding="ASCII")
self.is_initiator = False
def start(self, prime, generator, other_person):
self.is_initiator = True
self.prime = prime
self.generator = generator
self.private_key, self.public_key = (
generate_dh_keypair(prime, generator)
)
self.send_open_channel_request(other_person)
def send_open_channel_request(self, recipient):
recipient.recv_open_channel_request(
self,
self.prime,
self.generator,
self.public_key
)
def recv_open_channel_request(
self, sender, prime, generator, sender_public_key
):
self.private_key, self.public_key = (
generate_dh_keypair(prime, generator)
)
self.session_key = (
session_key(self.private_key, sender_public_key, prime)
)
self.send_open_channel_ack(sender)
def send_open_channel_ack(self, recipient):
recipient.recv_open_channel_ack(self, self.public_key)
def recv_open_channel_ack(self, sender, sender_public_key):
self.session_key = (
session_key(self.private_key, sender_public_key, self.prime)
)
self.send_message(sender, self.name_bytes + b" says hi")
def send_message(self, recipient, message):
iv = randbytes(16)
ctext = aes_128_cbc_encrypt(message, self.session_key, iv)
recipient.recv_message(self, ctext, iv)
def recv_message(self, sender, ctext, iv):
message = aes_128_cbc_decrypt(ctext, self.session_key, iv)
print(f"{self.name} received: {message.decode('ASCII')}")
if self.is_initiator:
return
iv = randbytes(16)
response = message + b", " + self.name_bytes + b" says hi back"
ctext = aes_128_cbc_encrypt(response, self.session_key, iv)
sender.recv_message(self, ctext, iv)
A = Person("Alice")
B = Person("Bob")
A.start(P, G, other_person=B)
Bob received: Alice says hi Alice received: Alice says hi, Bob says hi back
If the public key is set to $p$ (which is a little odd, as it's supposed to be a value modulo $p$, but let's roll with the idea), then the session key is predictable: $s = p^a \bmod p = 0$ for any private key $a$.
class MITM(Person):
def __init__(self, downstream_person):
super().__init__("MITM")
self.downstream_person = downstream_person
def recv_open_channel_request(
self, sender, prime, generator, sender_public_key
):
self.upstream_person = sender
self.prime = prime
self.generator = generator
self.private_key = 0 # arbitrary
self.public_key = prime # the weird part
self.session_key = key_value_to_bytes(0)
self.send_open_channel_request(self.downstream_person)
self.send_open_channel_ack(self.upstream_person)
def recv_open_channel_ack(self, sender, sender_public_key):
pass
def recv_message(self, sender, ctext, iv):
message = aes_128_cbc_decrypt(ctext, self.session_key, iv)
print(f"{self.name} intercepted: {message.decode('ASCII')}")
if sender == self.upstream_person:
other_person = self.downstream_person
else:
other_person = self.upstream_person
self.send_message(other_person, message)
A = Person("Alice")
B = Person("Bob")
A.start(P, G, other_person=MITM(downstream_person=B))
MITM intercepted: Alice says hi Bob received: Alice says hi MITM intercepted: Alice says hi, Bob says hi back Alice received: Alice says hi, Bob says hi back
A->B
Send "p", "g"
B->A
Send ACK
A->B
Send "A"
B->A
Send "B"
A->B
Send AES-CBC(SHA1(s)[0:16], iv=random(16), msg) + iv
B->A
Send AES-CBC(SHA1(s)[0:16], iv=random(16), A's msg) + iv
Do the MITM attack again, but play with "g". What happens with:
g = 1
g = p
g = p - 1
Write attacks for each.
When does this ever happen?
Honestly, not that often in real-world systems. If you can mess with "g", chances are you can mess with something worse. Most systems pre-agree on a static DH group. But the same construction exists in Elliptic Curve Diffie-Hellman, and this becomes more relevant there.
There's not much to do here. Setting $g$ to any of these values means that the session key is predictable. As the previous challenge admitted, a man-in-the-middle doesn't need to inject parameter values because it can just create session keys as normal. But for the record:
To understand SRP, look at how you generate an AES key from DH; now, just observe you can do the "opposite" operation and generate a numeric parameter from a hash. Then:
Replace A and B with C and S (client & server)
C & S
Agree on N=[NIST Prime], g=2, k=3, I (email), P (password)
S
1. Generate salt as random integer
2. Generate string xH=SHA256(salt|password)
3. Convert xH to integer x somehow (put 0x on hexdigest)
4. Generate v=g**x % N
5. Save everything but x, xH
C->S
Send I, A=g**a % N (a la Diffie Hellman)
S->C
Send salt, B=kv + g**b % N
S, C
Compute string uH = SHA256(A|B), u = integer of uH
C
1. Generate string xH=SHA256(salt|password)
2. Convert xH to integer x somehow (put 0x on hexdigest)
3. Generate S = (B - k * g**x)**(a + u * x) % N
4. Generate K = SHA256(S)
S
1. Generate S = (A * v**u) ** b % N
2. Generate K = SHA256(S)
C->S
Send HMAC-SHA256(K, salt)
S->C
Send "OK" if HMAC-SHA256(K, salt) validates
You're going to want to do this at a REPL of some sort; it may take a couple tries.
It doesn't matter how you go from integer to string or string to integer (where things are going in or out of SHA256) as long as you do it consistently. I tested by using the ASCII decimal representation of integers as input to SHA256, and by converting the hexdigest to an integer when processing its output.
This is basically Diffie Hellman with a tweak of mixing the password into the public keys. The server also takes an extra step to avoid storing an easily crackable password-equivalent.
The phrasing of this challenge, specifically in that the client and server "agree" on password $P$, is a little odd because the entire point of SRP is that the client never sends the password to the server. Instead, in a registration phase that is different from what is described above, the client sends just the identifying username $I$ and password verifier value $v$ to the server. Typically the client would also create and send the salt at the same time, though the salt can in principle be created by either party as long as it is shared. Either way, the server must return the salt during the login phase, as the client is not expected to remember it (the next challenge will take advantage of this fact).
The math works out as follows. Recall that $u$ is computed from the two public keys and $x$ is computed from the salt and password. The client computes (this is all modulo $N$):
$$ \begin{eqnarray*} S &=& (B-kv)^{a+ux} \\ &=& (B-kg^x)^{a+ux} \\ &=& (kv+g^b-kg^x)^{a+ux} \\ &=& (kg^x+g^b-kg^x)^{a+ux} \\ &=& (g^b)^{a+ux} \end{eqnarray*} $$Notice how, as with just basic Diffie-Hellman, the client is able to compute a quantity involving $b$ without knowing $b$, because $b$ is baked into $B$. The server computes:
$$ \begin{eqnarray*} S &=& (Av^u)^b \\ &=& (g^av^u)^b \\ &=& (g^a(g^x)^u)^b \\ &=& (g^b)^{a+ux} \end{eqnarray*} $$Similarly, the server is able to compute a quantity involving $x$ and $a$ without knowing them, because they're baked into $v$ and $A$, respectively.
N = P
K = 3
# In the following:
#
# a, A: client private/public keypair
# b, B: server private/public keypair (B tweaked)
# v: password verifier value
class Client:
def compute_xv(self, salt, password):
x = b2i(sha256(i2b(salt) + password))
v = modexp(G, x, N)
return x, v
def register_with_server(self, server, username, password):
salt = randint(2**255, 2**256-1)
_, v = self.compute_xv(salt, password)
server.register_user(username, v, salt)
def login(self, server, username, password):
a, A = generate_dh_keypair(N, G)
B, salt = server.initiate_login(username, A)
u = b2i(sha256(i2b(A) + i2b(B)))
x, v = self.compute_xv(salt, password)
S = modexp(B-K*v, a+u*x, N)
key = sha256(i2b(S))
hmac = hmac_sha256(key, i2b(salt))
keys_match = server.complete_login(username, hmac)
print(f"Login {'' if keys_match else 'un'}successful")
class Server:
class UserRecord:
# Admittedly, this class is a hodge-podge of persistent
# information (v, salt) and transactional information
# (A, b, B).
def __init__(self, v, salt):
self.v = v
self.salt = salt
self.A = None
self.b = None
self.B = None
def __init__(self):
self.users = {}
def register_user(self, username, v, salt):
self.users[username] = Server.UserRecord(v, salt)
def initiate_login(self, username, A):
r = self.users[username]
r.A = A
r.b, r.B = generate_dh_keypair(N, G)
# Tweak added to basic Diffie-Hellman
r.B = (r.B + K*r.v)%N
return r.B, r.salt
def complete_login(self, username, client_hmac):
r = self.users[username]
u = b2i(sha256(i2b(r.A) + i2b(r.B)))
S = modexp(r.A*modexp(r.v, u, N), r.b, N)
key = sha256(i2b(S))
server_hmac = hmac_sha256(key, i2b(r.salt))
return client_hmac == server_hmac
C = Client()
S = Server()
C.register_with_server(S, b"gjanee", b"2secret4u")
# Check that authentication works
C.login(S, b"gjanee", b"2secret4u")
# For good measure, check that authentication fails when it should
C.login(S, b"gjanee", b"wrong password")
Login successful Login unsuccessful
Get your SRP working in an actual client-server setting. "Log in" with a valid password using the protocol.
Now log in without your password by having the client send 0 as its "A" value. What does this do to the "S" value that both sides compute?
Now log in without your password by having the client send N, N*2, &c.
Cryptanalytic MVP award
Trevor Perrin and Nate Lawson taught us this attack 7 years ago. It is excellent. Attacks on DH are tricky to "operationalize". But this attack uses the same concepts, and results in auth bypass. Almost every implementation of SRP we've ever seen has this flaw; if you see a new one, go look for this bug.
If $A \equiv 0 \bmod N$ then the server computes $S = 0$ and key $K$ is the hash of $0$. Recall our observation in the previous challenge that the server supplies the salt. Thus the client can trivially compute HMAC-SHA256(0, salt) and pass the authentication test and, armed with the key, communicate with the server.
S
x = SHA256(salt|password)
v = g**x % n
C->S
I, A = g**a % n
S->C
salt, B = g**b % n, u = 128 bit random number
C
x = SHA256(salt|password)
S = B**(a + ux) % n
K = SHA256(S)
S
S = (A * v ** u)**b % n
K = SHA256(S)
C->S
Send HMAC-SHA256(K, salt)
S->C
Send "OK" if HMAC-SHA256(K, salt) validates
Note that in this protocol, the server's "B" parameter doesn't depend on the password (it's just a Diffie Hellman public key).
Make sure the protocol works given a valid password.
Now, run the protocol as a MITM attacker: pose as the server and use arbitrary values for b, B, u, and salt.
Crack the password from A's HMAC-SHA256(K, salt).
This challenge highlights that the use of salts does not protect against an offline dictionary attack by a man-in-the-middle. Salts are stored by the server and presented to the client, and hence are ultimately controlled by the server. So in the above scenario, an attacker can pick a (single) arbitrary salt value, and precompute $x$ (and from there $v$) for an entire dictionary of possible passwords, and then compare HMACs upon login attempt. SRP protects against this by incorporating $x$ into the computation of $B$ (and the client assumes that $x$ has been so incorporated, and its computation of the key and HMAC assume that this has been done).
K = 0 # Effectively remove K from computation
# From https://en.wikipedia.org/wiki/List_of_the_most_common_passwords
most_common_passwords = [
b"123456",
b"123456789",
b"12345",
b"qwerty",
b"password",
b"12345678",
b"111111",
b"123123",
b"1234567890",
b"1234567",
b"qwerty123",
b"000000",
b"1q2w3e",
b"aa12345678",
b"abc123",
b"password1",
b"1234",
b"qwertyuiop",
b"123321",
b"password123"
]
class FauxServer(Server):
def __init__(self):
# Two tweaks: we use a fixed salt value, and we ignore the
# password verifier value sent by the client.
self.fixed_salt = randint(2**255, 2**256-1)
self.users = defaultdict(lambda: Server.UserRecord(0, self.fixed_salt))
# Precompute a dictionary.
def compute_v(password):
x = b2i(sha256(i2b(self.fixed_salt) + password))
return modexp(G, x, N)
self.passwords = {
pw: compute_v(pw)
for pw in most_common_passwords
}
def register_user(self, username, v, salt):
pass
def complete_login(self, username, client_hmac):
r = self.users[username]
u = b2i(sha256(i2b(r.A) + i2b(r.B)))
for pw, v in self.passwords.items():
S = modexp(r.A*modexp(v, u, N), r.b, N)
key = sha256(i2b(S))
server_hmac = hmac_sha256(key, i2b(self.fixed_salt))
if server_hmac == client_hmac:
print(f"MITM: password is '{pw.decode('ASCII')}'")
return True
return False
C = Client()
S = FauxServer()
C.login(S, b"gjanee", choice(most_common_passwords))
MITM: password is '123321' Login successful
There are two annoying things about implementing RSA. Both of them involve key generation; the actual encryption/decryption in RSA is trivial.
First, you need to generate random primes. You can't just agree on a prime ahead of time, like you do in DH. You can write this algorithm yourself, but I just cheat and use OpenSSL's BN library to do the work.
The second is that you need an "invmod" operation (the multiplicative inverse), which is not an operation that is wired into your language. The algorithm is just a couple lines, but I always lose an hour getting it to work.
I recommend you not bother with primegen, but do take the time to get your own EGCD and invmod algorithm working.
Now:
Finally, to encrypt a string, do something cheesy, like convert the string to hex and put "0x" on the front of it to turn it into a number. The math cares not how stupidly you feed it strings.
In the RSA algorithm, as described here and elsewhere, primes $p$ and $q$ are chosen first, and are randomly chosen but otherwise arbitrary, and then exponent $e$ is chosen as any value that is coprime to $(p-1)(q-1)$. However, there are two nuances. First, the primes are not arbitrary, but in actual practice must be chosen with care. As the authors note in their original paper, "To gain additional protection against sophisticated factoring algorithms, $p$ and $q$ should differ in length by a few digits, both $(p-1)$ and $(q-1)$ should contain large prime factors, and $\gcd(p-1, q-1)$ should be small." Second, $e$ is not as arbitrary as it sounds either. We are given $e = 3$ here, but generally there are recommendations that $e$ be a "small" Fermat prime (i.e., of the form $2^{2^n}+1$) of which there are only a few. So it seems that $p$ and $q$ must be random but also chosen such that $p-1$ and $q-1$ are coprime to an already-chosen $e$. Our code below does this.
As for size recommendations, these have changed over time as computing power has increased. The aforementioned paper recommends 100-digit (~330-bit) primes, but nowadays (see, e.g., FIPS 186-5: Digital Signature Standard) 1,024-bit primes (yielding a 2,048-bit modulus) are recommended.
def is_prime(n, rounds=40):
# Miller-Rabin primality test for n >= 2
if n < 2: return False
if n <= 3: return True
if n%2 == 0: return False
s, d = 0, n-1
while d%2 == 0:
s += 1
d //= 2
for _ in range(rounds):
a = randint(2, n-1)
x = modexp(a, d, n)
for _ in range(s):
y = modexp(x, 2, n)
if y == 1 and x != 1 and x != n-1:
return False
x = y
if y != 1:
return False
return True
def random_rsa_prime(num_bits, e):
# Return prime p such that gcd(p-1, e) == 0
n = randint(2**(num_bits-1), 2**num_bits-1)
if n%2 == 0:
n += 1
while True:
if (n-1)%e != 0:
if is_prime(n):
return n
n += 2
# N.B.: `ptext` and `ctext` are integers in the following
def rsa_encrypt(e, n, ptext):
assert ptext < n
return modexp(ptext, e, n)
def rsa_decrypt(d, n, ctext):
return modexp(ctext, d, n)
e = 3
p = random_rsa_prime(1024, e)
q = random_rsa_prime(1024, e)
n = p*q
et = (p-1)*(q-1)
d = modinv(e, et)
# Try it out
message = b2i(b"A second lamp in the belfry burns!")
rsa_decrypt(d, n, rsa_encrypt(e, n, message)) == message
True
Assume you're a Javascript programmer. That is, you're using a naive handrolled RSA to encrypt without padding.
Assume you can be coerced into encrypting the same plaintext three times, under three different public keys. You can; it's happened.
Then an attacker can trivially decrypt your message, by:
The CRT says you can take any number and represent it as the combination of a series of residues mod a series of moduli. In the three-residue case, you have:
result =
(c_0 * m_s_0 * invmod(m_s_0, n_0)) +
(c_1 * m_s_1 * invmod(m_s_1, n_1)) +
(c_2 * m_s_2 * invmod(m_s_2, n_2)) mod N_012
where:
c_0, c_1, c_2 are the three respective residues mod
n_0, n_1, n_2
m_s_n (for n in 0, 1, 2) are the product of the moduli
EXCEPT n_n --- ie, m_s_1 is n_0 * n_2
N_012 is the product of all three moduli
To decrypt RSA using a simple cube root, leave off the final modulus operation; just take the raw accumulated result and cube-root it.
For plaintext $p$ and exponent $e=3$, we're given
$$ \begin{eqnarray*} c_0 &=& p^3 \bmod n_0 \\ c_1 &=& p^3 \bmod n_1 \\ c_2 &=& p^3 \bmod n_2 \\ \end{eqnarray*} $$The Chinese Remainder Theorem gives us $p^3 \bmod n_0 n_1 n_2$. Since $p < \{n_0, n_1, n_2\}$, then $p^3 < n_0 n_1 n_2$ and we are justified in recovering $p$ by taking the cube root of the value that results from the modulus operation with $n_0 n_1 n_2$. And this is the subtle reason why we needed to start with (at least) 3 ciphertexts. With only two ciphertexts, and with $e=3$, the Chinese Remainder Theorem would give us $p^3 \bmod n_0 n_1$ and it would not necessarily be the case that $p^3 < n_0 n_1$.
def integer_cube_root(x):
# For positive x
def f(n):
return n**3
r = 1
while f(r) <= x:
r *= 2
l = r//2
while l <= r:
m = (l+r)//2
if f(m) < x:
l = m+1
elif f(m) > x:
r = m-1
else:
return m
return None
n0 = random_rsa_prime(1024, e) * random_rsa_prime(1024, e)
n1 = random_rsa_prime(1024, e) * random_rsa_prime(1024, e)
n2 = random_rsa_prime(1024, e) * random_rsa_prime(1024, e)
c0 = rsa_encrypt(e, n0, message)
c1 = rsa_encrypt(e, n1, message)
c2 = rsa_encrypt(e, n2, message)
result = (
(
c0*n1*n2*modinv(n1*n2, n0) +
c1*n0*n2*modinv(n0*n2, n1) +
c2*n0*n1*modinv(n0*n1, n2)
)%(n0*n1*n2)
)
i2b(integer_cube_root(result))
b'A second lamp in the belfry burns!'