#!/usr/bin/env python
# -*- coding: utf-8 -*-
from Crypto.Util.number import *
import random
n = 2 ** 512
m = random.randint(2, n-1) | 1
c = pow(m, bytes_to_long(flag), n)
print 'm = ' + str(m)
print 'c = ' + str(c)
# m = 391190709124527428959489662565274039318305952172936859403855079581402770986890308469084735451207885386318986881041563704825943945069343345307381099559075
# c = 6665851394203214245856789450723658632520816791621796775909766895233000234023642878786025644953797995373211308485605397024123180085924117610802485972584499
函数释义:
random.randit(2,n-1):它只会在2到n-1中随机返回一个整数。
pow(m, bytes_to_long(flag), n): 函数是计算m的bytes_to_long(flag)次方,如果n在存在,则再对结果进行取模,其结果等效于
pow(m,bytes_to_long(flag)) %n
str()* 返回一个对象的string格式
该题的重点: c = pow(m, bytes_to_long(flag), n),由于已知:M,C,N
未知:bytes_to_long(flag)
由此可见这是密码学中一个基于求离散对数困难性的问题
解决方法:
# -*- coding: cp936 -*-
import random
import gmpy2
def discreteLog(g,p,a): #离散对数,求 g^x=a mod p中的x
table={}
sq=gmpy2.isqrt(p-1)
m=gmpy2.add(sq,1) #向上取整
for i in range(m):
k=-i*m
y=gmpy2.powmod(g,k,p)
mod=((a%p)*y)%p
table.update({mod:i})
j=0
while True:
result=gmpy2.powmod(g,j,p)
if result in table.keys():
sa=m*table[result]+j
return sa
#return table[result],m #将对应的下标返回
else:
j=j+1
g = 391190709124527428959489662565274039318305952172936859403855079581402770986890308469084735451207885386318986881041563704825943945069343345307381099559075
a = 6665851394203214245856789450723658632520816791621796775909766895233000234023642878786025644953797995373211308485605397024123180085924117610802485972584499
p = 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084096
x = discreteLog(g,p,a);
print(str(x));
mmp,数字太大了,溢出了,python跑不出来,我太菜了,还是等WP吧