从零开始学RSA:已知e,n,dp,c求m等4类问题解答

2024-04-11 12:12

本文主要是介绍从零开始学RSA:已知e,n,dp,c求m等4类问题解答,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

(13)已知e,n,dp,c求m

题目内容如下:

e=65537n=9637571466652899741848142654451413405801976834328667418509217149503238513830870985353918314633160277580591819016181785300521866901536670666234046521697590230079161867282389124998093526637796571100147052430445089605759722456767679930869250538932528092292071024877213105462554819256136145385237821098127348787416199401770954567019811050508888349297579329222552491826770225583983899834347983888473219771888063393354348613119521862989609112706536794212028369088219375364362615622092005578099889045473175051574207130932430162265994221914833343534531743589037146933738549770365029230545884239551015472122598634133661853901dp=81339405704902517676022188908547543689627829453799865550091494842725439570571310071337729038516525539158092247771184675844795891671744082925462138427070614848951224652874430072917346702280925974595608822751382808802457160317381440319175601623719969138918927272712366710634393379149593082774688540571485214097c=5971372776574706905158546698157178098706187597204981662036310534369575915776950962893790809274833462545672702278129839887482283641996814437707885716134279091994238891294614019371247451378504745748882207694219990495603397913371579808848136183106703158532870472345648247817132700604598385677497138485776569096958910782582696229046024695529762572289705021673895852985396416704278321332667281973074372362761992335826576550161390158761314769544548809326036026461123102509831887999493584436939086255411387879202594399181211724444617225689922628790388129032022982596393215038044861544602046137258904612792518629229736324827

解题脚本:

#!/usr/bin/python  #coding:utf-8  import gmpy2import libnumfrom Crypto.Util.number import long_to_bytese= 65537n = 9637571466652899741848142654451413405801976834328667418509217149503238513830870985353918314633160277580591819016181785300521866901536670666234046521697590230079161867282389124998093526637796571100147052430445089605759722456767679930869250538932528092292071024877213105462554819256136145385237821098127348787416199401770954567019811050508888349297579329222552491826770225583983899834347983888473219771888063393354348613119521862989609112706536794212028369088219375364362615622092005578099889045473175051574207130932430162265994221914833343534531743589037146933738549770365029230545884239551015472122598634133661853901c = 5971372776574706905158546698157178098706187597204981662036310534369575915776950962893790809274833462545672702278129839887482283641996814437707885716134279091994238891294614019371247451378504745748882207694219990495603397913371579808848136183106703158532870472345648247817132700604598385677497138485776569096958910782582696229046024695529762572289705021673895852985396416704278321332667281973074372362761992335826576550161390158761314769544548809326036026461123102509831887999493584436939086255411387879202594399181211724444617225689922628790388129032022982596393215038044861544602046137258904612792518629229736324827dp = 81339405704902517676022188908547543689627829453799865550091494842725439570571310071337729038516525539158092247771184675844795891671744082925462138427070614848951224652874430072917346702280925974595608822751382808802457160317381440319175601623719969138918927272712366710634393379149593082774688540571485214097for i in range(1,65538):if (dp*e-1)%i == 0:if n%(((dp*e-1)/i)+1)==0:p=((dp*e-1)/i)+1q=n/(((dp*e-1)/i)+1)phi = (p-1)*(q-1)d = gmpy2.invert(e,phi)%phim = pow(c,d,n)print long_to_bytes(m)

 (14)N分解出多个不同的因子

适用情况:题目给出的模数N可直接分解,但是分解之后得到了多个不同的因子

题目: 15-山东省大学生爱好者线上赛-上午RSA

题目给出一个文件里面的内容如下:

n= 544187306850902797629107353619267427694837163600853983242783

e= 39293

c= 439254895818320413408827022398053685867343267971712332011972

m=???

很明显n不大,可直接使用factordb进行分解。

E:\MISC\RSA\yafu-1.34>yafu-x64.exe "factor(544187306850902797629107353619267427694837163600853983242783)"fac: factoring 544187306850902797629107353619267427694837163600853983242783fac: using pretesting plan: normalfac: no tune info: using qs/gnfs crossover of 95 digitsdiv: primes less than 10000fmt: 1000000 iterationsrho: x^2 + 3, starting 1000 iterations on C60rho: x^2 + 2, starting 1000 iterations on C60rho: x^2 + 1, starting 1000 iterations on C60pm1: starting B1 = 150K, B2 = gmp-ecm default on C60ecm: 30/30 curves on C60, B1=2K, B2=gmp-ecm defaultecm: 10/49 curves on C60, B1=11K, B2=gmp-ecm defaultstarting SIQS on c43: 8035348176477081799669008169226677154776273==== sieving in progress (1 thread):     960 relations needed ========           Press ctrl-c to abort and save state           ====892 rels found: 450 full + 442 from 3656 partial, (21619.29 rels/sec)SIQS elapsed time = 0.2329 seconds.Total factoring time = 0.6579 seconds***factors found***P17 = 67724172605733871P20 = 11571390939636959887P24 = 694415063702720454699679ans = 1E:\MISC\RSA\yafu-1.34>

分解得到了3个因子,其实当时做这题时我也是一脸懵的,从没遇到过,试了n种方法,最后推到了这个方法。

解题脚本如下:

#!/usr/bin/python#coding:utf-8import gmpy2from Crypto.Util.number import long_to_bytesn= 544187306850902797629107353619267427694837163600853983242783e= 39293c= 439254895818320413408827022398053685867343267971712332011972p1 = 67724172605733871p2 = 11571390939636959887p3 = 694415063702720454699679phi = (p1-1)*(p2-1)*(p3-1)  d = gmpy2.invert(e, phi)  m = pow(c, d, n)  print long_to_bytes(m)

(15)LSB Oracle Attack

适用情况:可以通过选择输入的密文进而泄露最低位解题。

该攻击方式详细请参考该文章:

RSA Least-Significant-Bit Oracle Attack

​introspelliam.github.io/2018/03/27/crypto/RSA-Least-Significant-Bit-Oracle-Attack/

 题目: 14-SUCTF-RSA

正式进入rsa解题之前会让你提供一个字符串str,只有md5(str+给定的值salt) == 给定的部分哈希值part_hash,才能进入正式的题目。

然后,通过输入D,服务端会帮你解给出的给出的密文,但只会返回这个数是奇数(odd)还是偶数(even),通过G选项可以测试你输入的m是否正确,如果正确就会进入下1轮的

解题(3轮都是相同的原理,只是给出数c,n不同)(必须使用交互式解题)

解题脚本:

LSB Oracle Attack

​github.com/Mr-Aur0ra/RSA/blob/master/(15)LSB%20Oracle%20Attack/exp.py

本题摘自Nu1L战队提供的wp,膜,膜,膜

 (16)PKCS1_OAEP模式的RSA

西湖论剑2020--BrokenSystems。

题目给出三个文件,一个加密脚本BrokenSystems.py,一个密文文件message,一个RSA公钥文件public.key。

通过openssl查看,可以看到该公钥文件的e特别大,此时便存在rsa-wiener-attack攻击,通过此可以求出d。

通过rsa-wiener-attack求解d:

from Crypto.PublicKey import RSA

import ContinuedFractions, Arithmetic

def wiener_hack(e, n):

    # firstly git clone https://github.com/pablocelayes/rsa-wiener-attack.git !

    frac = ContinuedFractions.rational_to_contfrac(e, n)

    convergents = ContinuedFractions.convergents_from_contfrac(frac)

    for (k, d) in convergents:

        if k != 0 and (e * d - 1) % k == 0:

            phi = (e * d - 1) // k

            s = n - phi + 1

            discr = s * s - 4 * n

            if (discr >= 0):

                t = Arithmetic.is_perfect_square(discr)

                if t != -1 and (s + t) % 2 == 0:

                    print("First: Hacked d.")

                    return d

    return False

n = 0xC20745223FF5B94B2CD8412166F7288A21F2187E1A421453918CAB03C80253451233EB1BDC2363744228AA8694A8C2CBC833F80DDF40831A68901B230B83F3F0FED4B72D0B942B5E95DEDAC8DCC0047A2AFB90C81ED72D3AD49B72FC8BD0D3167DDDAA6AB5167C058DF36AF190B216085BBD9D621F9BD23A093E4E3D9CC387B6274F2C339C88E1B2D908ACB33F4E20E647ABEE0714A3CCE4646E896294B78103DCC9A4DB7ED681164C6E6CC7FD33476E174A6C707037B250491365F9F0EB76AEABA07DB2F662D88048AF98C88C76C6710DB9658D49FCA0CAF1F5CD99DC07F188432B48F85571168AD10FC824B7B682BAD6CAA5D12FF6F04C92786B738AB19BB7

e = 0x1d2d2f1f173f81cf368fec06d40d47fd92f8615c12eec14168f288427952b8cf5a538f70ba3341b6a173ae80375a96b0d384d9722b19149f78947375e0a33df5e693edabd5e4d44cffa9e525ea014f3fa499b5f7b29b219d90b88da55aae3a08637338d7bed056e3aec575be56bbde534b355a2e7757db7aeca96e78d67f21530b7c3ec24ac61f9b474ab283220dd9545135d065a724ce2f8f44e32e460eef5f9958009c58af595193d77e72c25f0cb01505b993c135328b11b500dcabc955c9177f839dd043586e25a31335e7d5437dc9e6cd6d4ebecb2937e16026c2792e1745f44eed5411beaab55ed0905db9198cbd431111be87462f46369e31d1a4613f

message = open('./message', 'r')

secret = message.read()

d = wiener_hack(e, n)

此时,我们便可以求出d。已知d,我们便可以求出p和q。

def getpq(n,e,d):

    p = 1

    q = 1

    while p==1 and q==1:

        k = d * e - 1

        g = random.randint ( 0 , n )

        while p==1 and q==1 and k % 2 == 0:

            k /= 2

            y = pow(g,k,n)

            if y!=1 and gcd(y-1,n)>1:

                p = gcd(y-1,n)

                q = n/p

    return p,q

因为加密脚本采用了PKCS1_OAEP模式下的RSA加密,所以我们需要通过手动构造私钥进而才可以去解密密文。采用原始的pow(c,d,n)是无法正确的解密密文的。

因此,我们需要先采用PKCS1_OAEP模式构造私钥,然后利用这个私钥来解密密文文件。

privkey = RSA.construct((long(n), long(e), long(d), long(p), long(q)))

key = PKCS1_OAEP.new(privkey)  

m = key.decrypt(secret)

print m

完整的exp如下:


#rsa-wiener-attack/exp1.py#!/usr/bin/python#coding:utf-8import gmpy2import randomfrom Crypto.PublicKey import RSAimport ContinuedFractions, Arithmeticfrom Crypto.Cipher import PKCS1_OAEPfrom Crypto.Util.number import long_to_bytesdef gcd(a, b):if a < b:a, b = b, awhile b != 0:temp = a % ba = bb = tempreturn adef getpq(n,e,d):p = 1q = 1while p==1 and q==1:k = d * e - 1g = random.randint ( 0 , n )while p==1 and q==1 and k % 2 == 0:k /= 2y = pow(g,k,n)if y!=1 and gcd(y-1,n)>1:p = gcd(y-1,n)q = n/preturn p,qdef wiener_hack(e, n):# firstly git clone https://github.com/pablocelayes/rsa-wiener-attack.git !frac = ContinuedFractions.rational_to_contfrac(e, n)convergents = ContinuedFractions.convergents_from_contfrac(frac)for (k, d) in convergents:if k != 0 and (e * d - 1) % k == 0:phi = (e * d - 1) // ks = n - phi + 1discr = s * s - 4 * nif (discr >= 0):t = Arithmetic.is_perfect_square(discr)if t != -1 and (s + t) % 2 == 0:print("First: Hacked d.")return dreturn Falsedef main():n = 0xC20745223FF5B94B2CD8412166F7288A21F2187E1A421453918CAB03C80253451233EB1BDC2363744228AA8694A8C2CBC833F80DDF40831A68901B230B83F3F0FED4B72D0B942B5E95DEDAC8DCC0047A2AFB90C81ED72D3AD49B72FC8BD0D3167DDDAA6AB5167C058DF36AF190B216085BBD9D621F9BD23A093E4E3D9CC387B6274F2C339C88E1B2D908ACB33F4E20E647ABEE0714A3CCE4646E896294B78103DCC9A4DB7ED681164C6E6CC7FD33476E174A6C707037B250491365F9F0EB76AEABA07DB2F662D88048AF98C88C76C6710DB9658D49FCA0CAF1F5CD99DC07F188432B48F85571168AD10FC824B7B682BAD6CAA5D12FF6F04C92786B738AB19BB7e = 0x1d2d2f1f173f81cf368fec06d40d47fd92f8615c12eec14168f288427952b8cf5a538f70ba3341b6a173ae80375a96b0d384d9722b19149f78947375e0a33df5e693edabd5e4d44cffa9e525ea014f3fa499b5f7b29b219d90b88da55aae3a08637338d7bed056e3aec575be56bbde534b355a2e7757db7aeca96e78d67f21530b7c3ec24ac61f9b474ab283220dd9545135d065a724ce2f8f44e32e460eef5f9958009c58af595193d77e72c25f0cb01505b993c135328b11b500dcabc955c9177f839dd043586e25a31335e7d5437dc9e6cd6d4ebecb2937e16026c2792e1745f44eed5411beaab55ed0905db9198cbd431111be87462f46369e31d1a4613fmessage = open('./message', 'r')secret = message.read()d = wiener_hack(e, n)p,q = getpq(n,e,d)#print p#print qprivkey = RSA.construct((long(n), long(e), long(d), long(p), long(q)))key = PKCS1_OAEP.new(privkey)  m = key.decrypt(secret)print mif __name__=="__main__":main()

注意,该脚本需要rsa-wiener-attack工具包的目录中执行,还需提前将密文文件message一同放到该目录下。

解题脚本如下:

基于rsa-wiener-attack解题

​github.com/Mr-Aur0ra/RSA/blob/master/(16)PKCS1_OAEP%E6%A8%A1%E5%BC%8F%E7%9A%84RSA/rsa-wiener-attack/exp1.py

以上是我当时做的步骤。

大佬们其实只要几行代码就可以解决,膜膜膜。

以下是ChaMd5团队给出的本题WriteUp(我进行了部分修改,便于理解):

维纳攻击,公钥文件中获取到e很大,利用维纳攻击可以拿到d。

维纳攻击

​github.com/pablocelayes/rsa-wiener-attack

然后利用e、d、n获取p、q,生成私钥文件:

#exp2.py

from Crypto.PublicKey import RSAfrom Crypto.Util.number import inverse, long_to_bytese = 3683191938452247871641914583009119792552938079110383367782698429399084083048335018186915282465581498846777124014232879019914546010406868697694661244001972931366227108140590201194336470785929194895915077935083045957890179080332615291089360169761324533970721460473221959270664692795701362942487885620152952927112838769014944652059440137350285198702402612151501564899791870051001152984815689187374906618917967106000628810361686645504356294175173529719443860140795170776862320812544438211122891112138748710073230404456268507750721647637959502454394140328030018450883598342764577147457231373121223878829298942493059211583d = 1779217788383673416690068487595062922771414230914791138743960472798057054853883175313487137767631446949382388070798609545617543049566741624609996040273727n = 24493816160588971749455534346389861269947121809901305744877671102517333076424951483888863597563544011725032585417200878377314372325231470164799594965293350352923195632229495874587039720317200655351788887974047948082357232348155828924230567816817425104960545706688263839042183224681231800805037117758927837949941052360649778743187012198508745207332696876463490071925421229447425456903529626946628855874075846839745388326224970202749994059533831664092151570836853681204646481502222112116971464211748086292930029540995987019610460396057955900244074999111267618452967579699626655472948383601391620012180211885979095636919p=163724217068973025857079545677048587508164102644298632911494474022224582218067057349189211462632427829087720476013052665037199232658015194718500750961261016558605363103092187533086949903145449057015220561698195502163792192055762108803714387175594231859738263839090338762578040513451585421537323416472060788989q=149604112324264915811376746906108325951188179904814259006959765070266946659481820938211689946210254302179197289522748397160602946376246768419310765669852537378426700376878745285639531531077237124655345323906476180103106894642043615024716862503414785057646920410083538192951872861366496901158348770066798098371keypair = RSA.generate(2048)keypair.p = pkeypair.q = qkeypair.e = ekeypair.n = nkeypair.d = dprivate_key = keypair.exportKey().decode('utf-8')f = open('pri.pem', 'w') #生成的私钥文件是pri.pem。f.write(private_key)

openssl解密即可。

详细的openssl使用方法可参考:

openssl常用命令,签名、非对称加解密 - kk Blog -- 通用基础

​abcdxyzk.github.io/blog/2018/02/09/tools-openssl/

这篇关于从零开始学RSA:已知e,n,dp,c求m等4类问题解答的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/894038

相关文章

hdu4826(三维DP)

这是一个百度之星的资格赛第四题 题目链接:http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1004&cid=500 题意:从左上角的点到右上角的点,每个点只能走一遍,走的方向有三个:向上,向下,向右,求最大值。 咋一看像搜索题,先暴搜,TLE,然后剪枝,还是TLE.然后我就改方法,用DP来做,这题和普通dp相比,多个个向上

hdu1011(背包树形DP)

没有完全理解这题, m个人,攻打一个map,map的入口是1,在攻打某个结点之前要先攻打其他一个结点 dp[i][j]表示m个人攻打以第i个结点为根节点的子树得到的最优解 状态转移dp[i][ j ] = max(dp[i][j], dp[i][k]+dp[t][j-k]),其中t是i结点的子节点 代码如下: #include<iostream>#include<algorithm

hdu4865(概率DP)

题意:已知前一天和今天的天气概率,某天的天气概率和叶子的潮湿程度的概率,n天叶子的湿度,求n天最有可能的天气情况。 思路:概率DP,dp[i][j]表示第i天天气为j的概率,状态转移如下:dp[i][j] = max(dp[i][j, dp[i-1][k]*table2[k][j]*table1[j][col] )  代码如下: #include <stdio.h>#include

usaco 1.1 Broken Necklace(DP)

直接上代码 接触的第一道dp ps.大概的思路就是 先从左往右用一个数组在每个点记下蓝或黑的个数 再从右到左算一遍 最后取出最大的即可 核心语句在于: 如果 str[i] = 'r'  ,   rl[i]=rl[i-1]+1, bl[i]=0 如果 str[i] = 'b' ,  bl[i]=bl[i-1]+1, rl[i]=0 如果 str[i] = 'w',  bl[i]=b

uva 10154 DP 叠乌龟

题意: 给你几只乌龟,每只乌龟有自身的重量和力量。 每只乌龟的力量可以承受自身体重和在其上的几只乌龟的体重和内。 问最多能叠放几只乌龟。 解析: 先将乌龟按力量从小到大排列。 然后dp的时候从前往后叠,状态转移方程: dp[i][j] = dp[i - 1][j];if (dp[i - 1][j - 1] != inf && dp[i - 1][j - 1] <= t[i]

uva 10118 dP

题意: 给4列篮子,每次从某一列开始无放回拿蜡烛放入篮子里,并且篮子最多只能放5支蜡烛,数字代表蜡烛的颜色。 当拿出当前颜色的蜡烛在篮子里存在时,猪脚可以把蜡烛带回家。 问最多拿多少只蜡烛。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cs

uva 10069 DP + 大数加法

代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vector>#include <queue>#include <map>#include <cl

uva 10029 HASH + DP

题意: 给一个字典,里面有好多单词。单词可以由增加、删除、变换,变成另一个单词,问能变换的最长单词长度。 解析: HASH+dp 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#inc

XTU 1233 n个硬币连续m个正面个数(dp)

题面: Coins Problem Description: Duoxida buys a bottle of MaiDong from a vending machine and the machine give her n coins back. She places them in a line randomly showing head face or tail face o

dp算法练习题【8】

不同二叉搜索树 96. 不同的二叉搜索树 给你一个整数 n ,求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种?返回满足题意的二叉搜索树的种数。 示例 1: 输入:n = 3输出:5 示例 2: 输入:n = 1输出:1 class Solution {public int numTrees(int n) {int[] dp = new int