基于分解N的RSA题目

基于分解N的RSA题目

1.在线查询分解网站

http://www.factordb.com/index.php

2.使用yafu工具分解

下载地址：https://sourceforge.net/projects/yafu/

#以分解49为例
yafu-x64.exe factor(49)

#导入文件进行分解，主要注意文本结尾要换行！！！不然要报错
yafu-x64.exe "factor(@)" -batchfile 1.txt 

3.使用费马分解（适用条件:p,q相近时）

脚本：

import gmpy2
p = gmpy2.next_prime(gmpy2.iroot(n,2)[0])
q = n // p

def isqrt(n):
  x = n
  y = (x + n // x) // 2
  while y < x:
    x = y
    y = (x + n // x) // 2
  return x

def fermat(n, verbose=True):
    a = isqrt(n) # int(ceil(n**0.5))
    b2 = a*a - n
    b = isqrt(n) # int(b2**0.5)
    count = 0
    while b*b != b2:
        # if verbose:
        #     print('Trying: a=%s b2=%s b=%s' % (a, b2, b))
        a = a + 1
        b2 = a*a - n
        b = isqrt(b2) # int(b2**0.5)
        count += 1
    p=a+b
    q=a-b
    assert n == p * q
    # print('a=',a)
    # print('b=',b)
    # print('p=',p)
    # print('q=',q)
    # print('pq=',p*q)
    return p, q
fermat(n) 
#分解出p,q之后利用利用脚本求解

出题脚本：

import libnum
import gmpy2

p=libnum.generate_prime(1024)
#下一个素数
q=gmpy2.next_prime(p)
print(p)
print(q)
print(gmpy2.is_prime(q))
e=65537
m="flag{20d6e2da95dcc1fa5f5432a436c4be18}"
m=libnum.s2n(m)
n=p*q
phi_n=(p-1)*(q-1)
d=libnum.invmod(e,phi_n)
c=pow(m,e,n)

print("n=",n)
print ("e=",e)
print ("c=",c)

解题脚本：

import  gmpy2
import libnum

def isqrt(n):
  x = n
  y = (x + n // x) // 2
  while y < x:
    x = y
    y = (x + n // x) // 2
  return x

def fermat(n, verbose=True):
    a = isqrt(n) # int(ceil(n**0.5))
    b2 = a*a - n
    b = isqrt(n) # int(b2**0.5)
    count = 0
    while b*b != b2:
        # if verbose:
        #     print('Trying: a=%s b2=%s b=%s' % (a, b2, b))
        a = a + 1
        b2 = a*a - n
        b = isqrt(b2) # int(b2**0.5)
        count += 1
    p=a+b
    q=a-b
    assert n == p * q
    # print('a=',a)
    # print('b=',b)
    print('p=',p)
    print('q=',q)
    # print('pq=',p*q)
    return p, q
n= 11236396438945464079176717143196471087880430124798640194523124584883161483744355761881720924798661332027501424643154414538029585287580122761405974427818841257794157497994556608202723391478027760181705924317533420305444809223444128034654367210331137068958693840582892819495487826045956577156074156668942232139402108462349340352898572481115406698318121299787982873916502591396884489682255184448165523604671743400422220149772905676655777228607948091675612455989601008858361759327370403306760674195506394280387024357322586732298060169962426894360775981877169895632927906390632063530920611197753716095903307467004289983267
e= 65537
c= 4260482466101011731957430920901406417434306478040387371588613512063428441001754753741853444857207349755032658064826592770143368278573527632514794087007140974732031358793249329430363014561312271335226315065519570861993052432656879088776144909638480994662696119431870831156129142403063675855781198930583825083362703887688501680905266707624440432914989795886392952354713859444836529227033324455920455610359249535012999943891644938239837207994673190694512955995798836266797112432609992164908679997257920566918693544746179908166741635316261624634351348613130319346356388546672516037747806222134853885202448682842353199133
pq=fermat(n)
p=pq[0]
q=pq[1]
phi_n=(p-1)*(q-1)
#求逆元
#d=libnum.invmod(e,phi_n)
d=gmpy2.invert(e,phi_n)
m=pow(c,d,n)
print(m)
print(libnum.n2s(int(m)).decode())