RSA解题

题目源码：

p=getPrime(1024)
q=getPrime(1024)
e=65537
n1=p*q
m=bytes_to_long(flag)
c1=pow(m,e,n1)
print (c1,e,n1)

p=getPrime(1024)
e=65537
n2=p*q
m=bytes_to_long("1"*32)
c2=pow (m,e,n2)
print (c2,e,n2)

这是一个RSA加密，我们先来了解下RSA
首先看这个加密算法的命名。很有意思，它其实是三个人的名字。早在1977年由麻省理工学院的三位数学家Rivest、Shamir 和 Adleman一起提出了这个加密算法，并且用他们三个人姓氏开头字母命名。
RSA加密算法是一种非对称加密算法，其玩法打破了以往所有加密算法的规则。在RSA出现之前，所有的加密方法都是同一种模式：加密解密的规则使用同一种方式。这种长达几个世纪的加密方案有一个致命的缺陷。在传递加密信息时，必须让对方拿到解密的规则才能正常解密。由于加密解密的规则一致，所以保存和传递"密钥"，就成了最头疼的问题。
RSA算法的步骤主要有以下几个步骤：
公钥与私钥的生成：
(1)随机挑选两个大质数 p 和 q，构造n = p * q (p ≠ q)；
(2)计算欧拉函数φ(n) = (p - 1) * (q - 1)；
(3)随机挑选整数e，使得gcd(e, φ(n)) = 1，即 e 与 φ(n) 互素； e 一般取65537 e ＜ φ(n)
(4)计算d，使得 e * d ≡ 1 mod φ(n)，即 d 是 e 的乘法逆元。
此时，公钥PU = (e, n)，私钥PR = (d, n)，公钥公开，私钥自己保管。
加密和解密：
C = fastExpMod(M , e , n)
M = fastExpMod(C , d , n)
核心：素性测试、扩展欧几里得算法、快速幂模算法
对于此题，加密的 q 是一样的，但是 p 不一样，所以只要将第一次加密的私钥 d 解出来，就可以将 flag 解密。要求出私钥 d ，就要求 phin1 。
所以，我们先求出最大公因子 q ，计算出 phin1 ，求出逆元 d ，再进行解密得到 m ，最终转换为字符串 flag 。

第一步：求出 n1 和 n2 的最大公因子 q

def gcd (a , b):
    if b == 0:
        return a
    else:
        return gcd (b , a % b)
n1 = 14967030059975114950295399874185047053736587880127990542035765201425779342430662517765063258784685868107066789475747180244711352646469776732938544641583842313791872986357504462184924075227433498631423289187988351475666785190854210389587594975456064984611990461126684301086241532915267311675164190213474245311019623654865937851653532870965423474555348239858021551589650169602439423841160698793338115204238140085738680883313433574060243600028500600824624358473403059597593891412179399165813622512901263380299561019624741488779367019389775786547292065352885007224239581776975892385364446446185642939137287519945974807727
n2 = 14624662628725820618622370803948630854094687814338334827462870357582795291844925274690253604919535785934208081825425541536057550227048399837243392490762167733083030368221240764693694321150104306044125934201699430146970466657410999261630825931178731857267599750324918610790098952520113593130245010530961350592735239454337631927669542026935873535964487595433984902529960726655481696404006628917922241666148082741874033756970724357470539589848548704573091633917869387239324447730587545472564561496724882799495186768858324490838169123077051890332313671220385830444331578674338014080959653201802476516237464651809255679979
q = gcd(n1, n2)
print ("q is:",q)

求出 q
在这里插入图片描述

第二步：计算 p1 和 phin1

p1 = n1 / q
phin1 = (q - 1) * (p1 - 1)

第三步：求出 d

import gmpy2
e = 65537
phin1 = 14967030059975114950295399874185047053736587880127990542035765201425779342430662517765063258784685868107066789475747180244711352646469776732938544641583842313791872986357504462184924075227433498631423289187988351475666785190854210389587594975456064984611990461126684301086241532915267311675164190213474245310765237418889818830227705394716496506798225956212671995034579858976755709275727545779323190399516673028337546107893321427344188693632154608029630011800092098274088483877499801049644118649183916488762975465398034665963727181218021502248431096169013010806582371790560686366315529215570889525939404997570002004720
d = gmpy2.invert (e, phin1)
print ("d is:",d)

求出 d
在这里插入图片描述

第四步：得到 flag

import libnum
d = 3966878437245643631637564975732704690837306124446086877872976205025646385675581853511438558449272831057566720069483322716185302889500282616707242022434828280064159692586323031389171478503753908040157812124377949328353938367107704570961998942943251122002994862593199357765354157601632561816952286250637771656438228389552713018311110406430345367091645709437632368795499521650765928713846948596775009799649123556193038678824282362527557831582015129491351042998117090300454963836491928898672785463727735926420386710315758459309854603319606229977802586942578329763497502143858265135463947731426008988290087504887177240673
c = 2482083893746618248544426737023750400124543452082436334398504986023501710639402060949106693279462896968839029712099336235976221571564642900240827774719199533124053953157919850838214021934907480633441577316263853011232518392904983028052155862154264401108124968404098823946691811798952747194237290581323868666637357604693015079007555594974245559555518819140844020498487432684946922741232053249894575417796067090655122702306134848220257943297645461477488086804856018323986796999103385565540496534422406390355987976815450744535949785073009043007159496929187184338592859040917546122343981520508220332785862546608841127597
n1 = 14967030059975114950295399874185047053736587880127990542035765201425779342430662517765063258784685868107066789475747180244711352646469776732938544641583842313791872986357504462184924075227433498631423289187988351475666785190854210389587594975456064984611990461126684301086241532915267311675164190213474245311019623654865937851653532870965423474555348239858021551589650169602439423841160698793338115204238140085738680883313433574060243600028500600824624358473403059597593891412179399165813622512901263380299561019624741488779367019389775786547292065352885007224239581776975892385364446446185642939137287519945974807727
m = pow(c, d, n1)
print (m)

在这里插入图片描述

转换为字符串

flag = libnum.n2s(m)
print (flag)

得到 flag:
在这里插入图片描述

附：这里用了两个库函数 gmpy2 和 libnum

利用 gmpy2 是为了求 e 对于 phin1 的乘法逆元得出私钥，当然也可以利用扩展欧几里得算法：

while(r > e):
    (c , d , k) = ext_gcd(e , r)       
    if d < 0:
        d = d + r

此时， d 就是私钥

安装步骤：
1.直接下载wheel文件
在github项目：https://github.com/aleaxit/gmpy/releases/tag/gmpy2-2.1.0a1
我下载的文件是：gmpy2-2.1.0a1-cp35-cp35m-win_amd64
2.检查是否安装了wheel
命令：pip install wheel
3.安装：pip install D:\gmpy2-2.1.0a1-cp35-cp35m-win_amd64