Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
RSA LSB Oracle Attack
def lsb_oracle_attack(n, e, c, lsb_oracle):
'''
RSA LSB Oracle Attack
:param lsb_oracle: lsb_oracle(x) == pow(x, d, n) % 2
:return: m or None if not found
'''
l, r, k2 = 0, 1, 1
while n * l // k2 + 1 < n * r // k2:
m = l + r
l <<= 1
r <<= 1
k2 <<= 1
if lsb_oracle(c * pow(k2, e, n) % n) == 1:
l = m
else:
r = m
m = n * l // k2
if pow(m, e, n) == c:
return m
m = n * r // k2
if pow(m, e, n) == c:
return m
return None
if __name__ == '__main__':
import random
def ex_gcd(m, n):
x, y, x1, y1 = 0, 1, 1, 0
while m % n:
x, x1 = x1 - m // n * x, x
y, y1 = y1 - m // n * y, y
m, n = n, m % n
return n, x, y
def inv(x, p):
g, y, k = ex_gcd(x, p)
if y < p:
y += p
return y
def gen_lsb_oracle(d, n):
def f(x):
return pow(x, d, n) % 2
return f
def test_lsboa(p, q):
e = 65537
d = inv(e, (p - 1) * (q - 1))
n = p * q
# print("p=%d q=%d n=%d e=%d d=%d" % (p, q, n, e, d))
decodefun = gen_lsb_oracle(d, n)
for i in range(1000):
m = random.randint(0, n - 1)
c = pow(m, e, n)
m1 = lsb_oracle_attack(n, e, c, decodefun)
if m != m1:
print("Wrong (p, q, n, m)")
print(p)
print(q)
print(n)
print(m)
exit(0)
print(p, q, "OK")
prime = [3, 5, 7, 11, 13, 127, 229, 5591, 26399, 13044247, 16085599, 506823809, 1555336697, 1000000007, 1000000009]
for i in range(len(prime)):
for j in range(i):
test_lsboa(prime[j], prime[i])
test_lsboa(prime[i], prime[j])
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.