RSA0-1

理论介绍

基本原理

欧拉函数

欧拉函数φ(n):是小于n的自然数中与n互质的数的个数

φ(n)的计算方法并不复杂，但是为了得到最后那个公式，需要一步步讨论:
第一种：n=1        φ(1) = 1
第二种：n是质数    φ(n)=n-1    质数与小于它的每一个数都构成互质关系
第三种：n=p^k(p为质数，k为正整数φ(n)=φ(p^k)=p^k-p^(k-1)=p^k*(1-1/p)
只有当一个数不包含质数p,才可能与n互质，而包含质数p的数一共有p^(k-1)个，即1*k、2*k、...p^(k-1)*k
第四种：n可以分解成两个互质的整数之积φ(n)=φ(p1*p2)=φ(p1)*φ(p2)(中国剩余定理)
最终推理:
n=p1^k1*p2^k2*p3^k3...pr^kr(任意一个大于1的正整数,都可以写成质数的积)
由4得:φ(n)=φ(p1^k1)*φ(p1^k2)...φ(pr^kr)
由3得:φ(n)=p1^k1*p2^k2...pr^kr*(1-1/p1)*(1-1/p2)..*(1-1/pr)
所以:φ(n)=n*(1-1/p1)*(1-1/p2)*...(1-1/pr)

φ(n)=n*(1-1/p1)*(1-1/p2)*...(1-1/pr)

欧拉定理

a^φ(n)≡1 (mod n) a和n互质

费马小定理(欧拉定理的特例)

a^(p-1)≡1(mod p) p是质数,a,p互质

模反元素(逆元)

a*b≡1(mod n) a,n互质
a mod n的逆元是使 a * b mod n = 1 的最小的b

模运算

四则运算:
(a + b) % p = (a % p + b % p) % p
(a - b) % p = (a % p - b % p) % p
(a * b) % p = (a % p * b % p) % p
a ^ b % p = ((a % p) ^ b) % p
结合律:
((a + b) % p + c) = (a + (b + c) % p) % p
((a * b) % p * c) = (a * (b * c) % p) % p
交换律:
(a + b) % p = (b + a) % p
(a * b) % p = (b * a) % p
分配律:
(a + b) % p = (a % p + b % p) % p
((a + b) % p * c) % p = ((a * c) % p + (b * c) % p
重要定理:
若 a ≡ b (mod p)，则对于任意的 c，都有(a + c) ≡ (b + c) (mod p)
若 a ≡ b (mod p)，则对于任意的 c，都有(a * c) ≡ (b * c) (mod p)
若 a ≡ b (mod p)，c ≡ d (mod p)，则:
(a + c) ≡ (b + d) (mod p)
(a - c) ≡ (b - d) (mod p)
(a * c) ≡ (b * d) (mod p)
(a / c) ≡ (b / d) (mod p)

解释原理

1：c=m^e%N        加密
2：m=c^d%N        解密

将1带入2: m = (m ^ e % N ) ^ d % N
需要证明: m == ( m ^ e % N ) ^ d % N

(m^e%N)^d%N
=> (m^e)^d%N
=> m^(e*d)%N 因为e * d ≡ 1 (mod φ(N))所以e*d=K*φ(N)+1
=> (m^(K*φ(N)+1))%N
=> (m^(K*φ(N)*m)%N
=> ((m^φ(N)^K%N*m)%N
=> ((m^φ(N)^K%N*m%N)%N
=> ((m^φ(N)%N)^K%N*m%N)%N
=> (1^K%N*m%N)%N 欧拉定理：a^φ(n)≡1 mod n
=> (m%N)%N
=> m%N m<N
=> m

基本过程

第一步，随机选择两个不相等的质数p和q。
第二步，计算p和q的乘积n。
第三步，计算n的欧拉函数φ(n)。
第四步，随机选择一个整数e，条件是1< e < φ(n)，且e与φ(n) 互质。
第五步，计算e对于φ(n)的模反元素d。
第六步，将n和e封装成公钥，n和d封装成私钥。

RSA算法的可靠性

回顾上面的密钥生成步骤，一共出现六个数字：p,q,n,φ(n),e,d
这六个数字之中，公钥用到了两个（n和e），其余四个数字都是不公开的。其中最关键的是d，因为n和d组成了私钥，一旦d泄漏，就等于私钥泄漏。

那么，有无可能在已知n和e的情况下，推导出d？
　　（1）ed≡1 (mod φ(n))。只有知道e和φ(n)，才能算出d。
　　（2）φ(n)=(p-1)(q-1)。只有知道p和q，才能算出φ(n)。
　　（3）n=pq。只有将n因数分解，才能算出p和q。
结论：如果n可以被因数分解，d就可以算出，也就意味着私钥被破解。

可是，大整数的因数分解，是一件非常困难的事情。目前，除了暴力破解，还没有发现别的有效方法。维基百科这样写道：
“对极大整数做因数分解的难度决定了RSA算法的可靠性。换言之，对一极大整数做因数分解愈困难，RSA算法愈可靠。
假如有人找到一种快速因数分解的算法，那么RSA的可靠性就会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的RSA密钥才可能被暴力破解。到2008年为止，世界上还没有任何可靠的攻击RSA算法的方式。
只要密钥长度足够长，用RSA加密的信息实际上是不能被解破的。”

基础实战

基础出题脚本

import libnum

#生成随机素数
p=libnum.generate_prime(1024)
q=libnum.generate_prime(1024)
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("p=",p)
print("q=",q)
print ("n=",n)
print("d=",d)
print ("e=",e)
print ("c=",c)

基础解题脚本

已知n,d,e,c求m

import libnum

n= 14685532699024100754723222996385121368294636639693750794149020559314539676501066491415844320990799035552463714403031072164829458702780715523923962246149328887690893262271480633736651143634392056066729487305166335857950659680699210683976952113003674104898343893168719508462975991580551696824510044412974267585312807460664570245139015568859112921920860421973308538800641652781742897528769692264955229878206911313791989518088100099218315995549914435278654377368771668058107642713121127495780090852489015591581414806590111818355121157794129813430710822697558144598815860067978324469091074823400715400666808772858128261149
d= 10655677501818714057545408290692306276248758047017058020876274084213258239416744966450976471246402284779991562186357882946337721435118045765127426899173581894141706933500094886492805160951008521020815528782559085235105783294876017603112074153984218299742602608478449101819428678878037976091306073545785820932796422483686522431260926680891531210950251782422010888047909274618007401655588566411972291526501884077240225819170340160706732901152519829956055255218835518533347875405883278225018714890042991619568316304958478955576005445279807142753050999269866987221510643119355301877102904394259290548609330522059178100989
e= 65537
c= 7937297427288435728721973474925856865675225171317301007619581716746999628275946964127516634203401830643076435690247635478297903236185011960902817030042080567027165802992734580344202744697251074454156026031417427325660809453340428989949816426637434868049018580855865080715251672252410696685286047485204432648545886024276695749435709592994477514818763551176789963387889424072650811645828675090859926233585219662579177051353763021116106877502871331756544361402971459889233069752657661921397258845893293005099736406362733668960163109452223071514272504206470939914043855546880424121530822318600645513435826636440478681928

m=pow(c, d, n)
print(libnum.n2s(m).decode())

已知p,q,e,c求m

import libnum

p= 178974110759313878895493455207516672882434662571655460770401953730906926302476821805659378622536968418528094957044346203494793341636459433763427491907849563922785749794854266865548657682445692416895365631610849027415100889893466490767087266542637440212533807985124840688092762928583845838066174446047886496977
q= 93610871651220602641323046206103959524660743045950590135111801621145944725719667412027010040112514078098465817329474817485502356054795293086881519931215167856745860801666777619204160653243683622930567962804914581845602027547589056026105213437044768786486688576038889017989891165091320977401144724582916902269
e= 65537
c= 10505609204533893330224001468185225454647695615253006709365840521320011117703729471412769493857753605106376689659952882885215696765275778768339621441610719177208351696489476567331875339672513868473669863672226315682278831184868041476134806131989809014422520472566202048041013413698358733781909446846787304422628166599338803127610040714545537436536348608012176828441837378861024372912755344397449657260043057239911064546424582314518819235470388313710641962070846850292694572345451390561142917224092435026246696084949470913298543523893386679712766629009873176804118782436042080621119334193337953451160118095182279971122

n=p*q
phi_n=(p-1)*(q-1)

#求逆元
d=libnum.invmod(e,phi_n)

m=pow(c,d,n)
print(m)
#数字转字节，转字符串
print(libnum.n2s(int(m)).decode())

暴力分解n的RSA

1.在线查询分解网站

2.使用yafu工具分解

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

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

3.使用费马小定理

适用于p和q接近的情况

原理

#分解函数
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)
分解出来后用脚本解密
import gmpy2
import libnum

p=
q=
e=
c=

n=p*q
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())

出题脚本

import libnum
import gmpy2

p=libnum.generate_prime(1024)
#下一个素数
q=gmpy2.next_prime(p)
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 ("p=",p)
print ("q=",q)
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)  #通过脚本或工具分解出q,p
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())

RSA密钥生成与读取

安装pycryptodome模块

公钥生成

from Crypto.PublicKey import RSA

p= 787228223375328491232514653709
q= 814212346998672554509751911073
n= 640970939378021470187479083920100737340912672709639557619757
d= 590103645243332826117029128695341159496883001869370080307201
e= 65537


rsa_components = (n, e)
keypair = RSA.construct(rsa_components)
with open('pubckey.pem', 'wb') as f :
    f.write(keypair.exportKey())

私钥生成

from Crypto.PublicKey import RSA

p= 787228223375328491232514653709
q= 814212346998672554509751911073
n= 640970939378021470187479083920100737340912672709639557619757
d= 590103645243332826117029128695341159496883001869370080307201
e= 65537


rsa_components = (n,e,d,p,q)
keypair = RSA.construct(rsa_components)
with open('private1.pem', 'wb') as f :
    f.write(keypair.exportKey())

公钥读取

from Crypto.PublicKey import RSA
with open("pubckey.pem","rb") as f:
    key = RSA.import_key(f.read())
    print('n = %d' % key.n)
    print('e = %d' % key.e)

私钥读取

from Crypto.PublicKey import RSA
with open("private1.pem","rb") as f:
    key = RSA.import_key(f.read())
    print('n = %d' % key.n)
    print('e = %d' % key.e)
    print('d = %d' % key.d)
    print('p = %d' % key.p)
    print('q = %d' % key.q)

出题脚本-基于N分解的题目

import libnum
import gmpy2
from Crypto.PublicKey import RSA

p=libnum.generate_prime(1024)
#下一个素数
q=int(gmpy2.next_prime(p))
e=65537
m="flag{a272722c1db834353ea3ce1d9c71feca}"
m=libnum.s2n(m)
n=p*q
c=pow(m,e,n)
flag_c=libnum.n2s(c)
rsa_components = (n, e)
keypair = RSA.construct(rsa_components)
with open('pubckey1.pem', 'wb') as f :
    f.write(keypair.exportKey())
with open("flag.txt","wb") as f:
    f.write(flag_c)

解题脚本

import libnum
import gmpy2
from Crypto.PublicKey import RSA


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


with open("pubckey1.pem","rb") as f:
    key = RSA.import_key(f.read())
    n=key.n
    e=key.e

with open("flag.txt","rb") as f:
    c=f.read()
    c=libnum.s2n(c)

#费马分解
n1=fermat(n)
p=n1[0]
q=n1[1]
phi_n=(p-1)*(q-1)
#求逆元
d=libnum.invmod(e,phi_n)
m=pow(c,d,n)
print(m)
print(libnum.n2s(int(m)).decode())

自动生成密钥并加密

from Crypto.Cipher import PKCS1_v1_5
from Crypto import Random
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP


random_generator = Random.new().read
rsa = RSA.generate(2048, random_generator)
# 生成私钥
private_key = rsa.exportKey()
# print(private_key.decode('utf-8'))
with open('rsa_private_key.pem', 'wb')as f:
    f.write(private_key)
# 生成公钥
public_key = rsa.publickey().exportKey()
# print(public_key.decode('utf-8'))
with open('rsa_public_key.pem', 'wb')as f:
    f.write(public_key)


#测试用密钥加密
public_key = RSA.importKey(public_key)
msg='flag'
pk = PKCS1_v1_5.new(public_key)
encrypt_text = pk.encrypt(msg.encode())
print(encrypt_text)

#测试密钥解密
private_key = RSA.importKey(private_key)
pk = PKCS1_v1_5.new(private_key)
msg = pk.decrypt(encrypt_text,0)
print(msg)


#两种标准
rsa_components = (n, e, int(d), p, q)
arsa = RSA.construct(rsa_components)
rsakey = RSA.importKey(arsa.exportKey())
rsakey = PKCS1_OAEP.new(rsakey)
decrypted = rsakey.decrypt(c)
print(decrypted)

------本文已结束，感谢您的阅读------