网鼎杯2020-Crypto(you raise me up)基于离散对数求解问题pythonqq41814777的博客-

#!/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吧