P10.低加密指数广播攻击
P10.低加密指数广播攻击
如果选取的加密指数较低,并且使用了相同的加密指数给一个接受者的群发送相同的信息,那么可以进行广播攻击得到明文。
在CTF中,n、c不同,明文m,e相同,其e比较小。使用中国剩余定理求解
出题脚本
随机生成flag
import random
import hashlib
import string
#字符串列表
a=string.printable
#随机生成flag
for i in range(10):
flag = ""
for i in range(10):
flag += a[random.randint(0, 99)]
flag = hashlib.md5(flag.encode()).hexdigest()
print("flag{" + flag + "}")
题目
import libnum
#生成随机素数
def rsa_def(e,m):
p=libnum.generate_prime(1024)
q=libnum.generate_prime(1024)
#字符串转数字
m=libnum.s2n(m)
n=p*q
c=pow(m,e,n)
n_lt.append(n)
c_lt.append(c)
n_lt=[]
c_lt=[]
e=23
m='flag{2cb2eb4b2c7fdf4e94e10344be856446}'
for i in range(7):
rsa_def(e,m)
print("e=",e)
print("n=",n_lt)
print("c=",c_lt)
解密脚本
解密脚本1
import libnum
from gmpy2 import invert, gcd, iroot
def op(x):
res = 1
for i in x:
res *= i
return res
def CRT(m, a):
assert (len(m) == len(a))
M = op(m)
sum = 0
for m, a in zip(m, a):
Mi = M // m
ti = invert(Mi, m)
sum += a * ti * Mi
return sum % M
def GCRT(m, a):
assert (len(m) == len(a))
curm, cura = m[0], a[0]
for m, a in zip(m[1:], a[1:]):
d = gcd(curm, m)
c = a - cura
assert (c % d == 0)
K = c // d * invert(curm // d, m // d)
cura += curm * K
curm = curm * m // d
return cura % curm
e= 23
n=[]
c=[]
m = CRT(n, c)
m1 = iroot(m, e) # 开e次方
print(m1)
print(libnum.n2s(int(m1[0])))
解密脚本2
import binascii,gmpy2
from functools import reduce
import libnum
def CRT(mi, ai):
assert(reduce(gmpy2.gcd,mi)==1)
assert (isinstance(mi, list) and isinstance(ai, list))
M = reduce(lambda x, y: x * y, mi)
ai_ti_Mi = [a * (M // m) * gmpy2.invert(M // m, m) for (m, a) in zip(mi, ai)]
return reduce(lambda x, y: x + y, ai_ti_Mi) % M
e= 23
n=[]
c=[]
m=gmpy2.iroot(CRT(n, c), e)[0]
print(m)
print(libnum.n2s(int(m)))