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

   日期:2020-05-11     浏览:630    评论:0    
核心提示:#!/usr/bin/env python# -*- coding: utf-8 -*-from Crypto.Util.number import *import randomn = 2 ** 512m = random.randint(2, n-1) | 1c = pow(m, bytes_to_long(flag), n)print m = + str(m)print c = + str(c)# m = 39119070912452742895948966256527python
#!/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吧

 
打赏
 本文转载自:网络 
所有权利归属于原作者,如文章来源标示错误或侵犯了您的权利请联系微信13520258486
更多>最近资讯中心
更多>最新资讯中心
0相关评论

推荐图文
推荐资讯中心
点击排行
最新信息
新手指南
采购商服务
供应商服务
交易安全
关注我们
手机网站:
新浪微博:
微信关注:

13520258486

周一至周五 9:00-18:00
(其他时间联系在线客服)

24小时在线客服