P99 零散知识点

高位攻击

from gmpy2 import *
from Crypto.Util.number import *
def low_exponent(n,e,c):
    k=0
    while True:
        a=iroot(c+k*n,e)
        if a[1]:
            return long_to_bytes(a[0])
        k+=1

def Common_modulus(e1,e2,n,c1,c2):
    _,r,s=gcdext(e1,e2)
    m=pow(c1,r,n)*pow(c2,s,n) %n
    return long_to_bytes(m)

def Partial_p(n,e,c,pbar,kbits):
    PR.<x> = PolynomialRing(Zmod(n))
    f = x + pbar
    x0 = f.small_roots(X=2^kbits, beta=0.4)[0]  # find root < 2^kbits with factor >= n^0.4
    p = x0 + pbar
    q = n // int(p)
    d = inverse_mod(e, (p-1)*(q-1))
    return long_to_bytes(pow(c, d, n))

c=19105765285510667553313898813498220212421177527647187802549913914263968945493144633390670605116251064550364704789358830072133349108808799075021540479815182657667763617178044110939458834654922540704196330451979349353031578518479199454480458137984734402248011464467312753683234543319955893
n=123814470394550598363280518848914546938137731026777975885846733672494493975703069760053867471836249473290828799962586855892685902902050630018312939010564945676699712246249820341712155938398068732866646422826619477180434858148938235662092482058999079105450136181685141895955574548671667320167741641072330259009
e=3
msg1=low_exponent(n,e,c)

c1=54995751387258798791895413216172284653407054079765769704170763023830130981480272943338445245689293729308200574217959018462512790523622252479258419498858307898118907076773470253533344877959508766285730509067829684427375759345623701605997067135659404296663877453758701010726561824951602615501078818914410959610
c2=91290935267458356541959327381220067466104890455391103989639822855753797805354139741959957951983943146108552762756444475545250343766798220348240377590112854890482375744876016191773471853704014735936608436210153669829454288199838827646402742554134017280213707222338496271289894681312606239512924842845268366950
e1=17
e2=65537
n=111381961169589927896512557754289420474877632607334685306667977794938824018345795836303161492076539375959731633270626091498843936401996648820451019811592594528673182109109991384472979198906744569181673282663323892346854520052840694924830064546269187849702880332522636682366270177489467478933966884097824069977
msg2=Common_modulus(e1,e2,n,c1,c2)

kbits=200
pbar=7117286695925472918001071846973900342640107770214858928188419765628151478620236042882657992902*2^200
n=113432930155033263769270712825121761080813952100666693606866355917116416984149165507231925180593860836255402950358327422447359200689537217528547623691586008952619063846801829802637448874451228957635707553980210685985215887107300416969549087293746310593988908287181025770739538992559714587375763131132963783147
e=65537
c=59213696442373765895948702611659756779813897653022080905635545636905434038306468935283962686059037461940227618715695875589055593696352594630107082714757036815875497138523738695066811985036315624927897081153190329636864005133757096991035607918106529151451834369442313673849563635248465014289409374291381429646
msg3=Partial_p(n,e,c,pbar,kbits)

msg=msg1+msg2+msg3
import hashlib
print("CISCN{"+hashlib.md5(msg).hexdigest()+"}")

离散对数

如果对于一个整数b和质数p的一个原根a，可以找到一个唯一的指数i，使得：

b=a**i%p 其中 0<i<p-1 成立，那么指数i称为b的以a为基数的模p的离散对数。

离散对数难题是指：当已知一个大质数p和它的一个原根a，如果给定一个b，要计算i的值是相当困难的。

e=sympy.discrete_log(n,c,m)

整数和字符串互转

#pip install pycryptodome

from Crypto.Util.number import long_to_bytes,bytes_to_long
print(bytes_to_long("123".encode()))
print(long_to_bytes(3224115).decode())

import libnum
print(libnum.s2n("123"))
print(libnum.n2s(3224115).decode())

计算

import libnum
import gmpy2
#求逆元
libnum.invmod(5, 26)
gmpy2.invert(5, 26)

#求最大公约数
libnum.gcd(2,4)
gmpy2.gcd(2, 4)

#扩展欧几里得求逆元
libnum.xgcd(5, 26)  # xgcd(a,b)返回：x,y,g ；ax+by=g
gmpy2.gcdext(5,26) # xgcd(a,b)返回：x,y,g ；ax+by=g

#开几次方根
libnum.nroot(16,2)
gmpy2.iroot(16,2)

#生成素数
libnum.generate_prime(4)
from Crypto.Util.number import getPrime
getPrime(30)

#相邻的下一个素数
gmpy2.next_prime()
#判断是否为素数
gmpy2.is_prime()

rsa库

import rsa
(pubkey, privkey) = rsa.newkeys(1024)
m = "flag".encode('utf-8')
c=rsa.encrypt(m,pubkey)
m=rsa.decrypt(c,privkey)
print(m)

公钥文件查看

import rsa
with open('publickey.pem',mode='rb') as f:
    keydata= f.read()
pubckey = rsa.PublicKey.load_pkcs1_openssl_pem(keydata)
pubckey.n
pubckey.e

from Crypto.PublicKey import RSA
path = '<key file path here>'
with open(path) as f:
    key = RSA.import_key(f.read())
    print('e = %d' % key.e)
    print('n = %d' % key.n)

根据私钥文件读取公钥加密后密文方式

import rsa
prikey = rsa.PrivateKey(n , e , d , p , q)
with open("test.enc" , "rb") as fp:
    print(rsa.decrypt(fp.read(), prikey).decode())

私钥

import math
import sys
from Crypto.PublicKey import RSA

rsa_components=(n,e,int(d),p,q)

keypair=RSA.construct(rsa_components)

private = open('private.pem', 'wb')
private.write(keypair.exportKey())
private.close()

pyCryptodome库

from Crypto.Util import number
s='this is a demo'
#字节转换为long型整数
ls=number.bytes_to_long(s)

bits=8*len(s)
#生成长度为bits的素数
gp=number.getPrime(bits)

#生成长度小于bits的随机数
gri=number.getRandomInteger(bits)

#生成长度为bits的随机数
grnbi=number.getRandomNBitInteger(bits)

#生成长度不超过bits的随机数
grn=number.getRandomNumber(bits)

#生成grn与2*grn之间的随机数
grr=number.getRandomRange(grn,2*grn)

#生成强的素数（gsp-1，gsp+1均至少具有一个大的素因子）
gsp=number.getStrongPrime(1024)

#计算gri在模grn下的逆
iin=number.inverse(gri,grn)

#判断iin是否为素数
ip=number.isPrime(iin)

#long型整数转换为字节
tb=number.long_to_bytes(ls)

sympy

sympy.prime(n)返回第n个素数

sympy.isprime(n)素性检测

sympy.primepi(n)返回小于n的素数的总数

sympy.nextprime(89)返回下一个素数，这里结果是97

sympy.prevprime(96)或sympy.prevprime(97)返回上一个素数，结果都是89

sympy.randprime(1,30)返回1到30之间的一个大于等于1小于30的随机素数 range [a, b)

sage中求解离散对数

https://blog.csdn.net/ckm1607011/article/details/106849551

sage中求解离散对数我目前知道的四个函数：

(1)discrete_log：通用的求离散对数的方法：discrete_log(a,base,ord,operation)

(2)discrete_log_rho：求离散对数的Pollard-Rho算法：discrete_log_rho(a,base,ord,operation)

(3)discrete_log_lambda：求离散对数的Pollard-kangaroo算法（也称为lambda算法）：discrete_log_lambda(a,base,bounds,operation)

(4)bsgs：小步大步法：bsgs(base,a,bounds,operation)

整个就是一个rsa加密，首先产生256比特的素数p,q，

对于10进制的长度为77或者78

然后将p,q分别拼接为P,Q。
也就是说P={10}^xp+q,Q={10}^yq+p，
其中x,y取77或78。
N=PQ={10}^{(x+y)}pq+{10}^xp^2+{10}^yq^2+pq,设n=pq
首先x,y\in[77,78]所以显然N的低z=min\{x,y\}就是n的低z位。
其次pq,p^2,q^2是一个量级的，而{10}^{(x+y)}足够大，所以N的高z\in[76,77,78]即为n的高z位
并且n的长度l\in[154,155,156]，所以说一般只有中间一到两位未知，直接爆破求到n
然后带回N={10}^{(x+y)}pq+{10}^xp^2+{10}^yq^2+pq得到一个一元四次方程:
f(q)={10}^yq^4+n({10}^{(x+y)}+1)q^2+{10}^xn^2=0直接利用求根公式解即可。

\[ \sum_{\mathclap{1\le i\le j\le n}} x_{ij } \]