ctfshow-unusualrsa1

1 题解

下载的代码如下

# ********************
# @Author: Lazzaro
# ********************

from Crypto.Util.number import getPrime,bytes_to_long,long_to_bytes
from random import randint
from secret import flag

p = getPrime(1024)
q = getPrime(1024)
n = p*q
print(n)

m = bytes_to_long(long_to_bytes(randint(0,30))*208+flag)
assert(m.bit_length()==2044)
print((m>>315)<<315)
c = pow(m,3,n)
print(c)

#14113948189208713011909396304970377626324044633561155020366406284451614054260708934598840781397326960921718892801653205159753091559901114082556464576477585198060530094478860626532455065960136263963965819002575418616768412539016154873800614138683106056209070597212668250136909436974469812231498651367459717175769611385545792201291192023843434476550550829737236225181770896867698281325858412643953550465132756142888893550007041167700300621499970661661288422834479368072744930285128061160879720771910458653611076539210357701565156322144818787619821653007453741709031635862923191561438148729294430924288173571196757351837
#1520800285708753284739523608878585974609134243280728660335545667177630830064371336150456537012842986526527904043383436211487979254140749228004148347597566264500276581990635110200009305900689510908049771218073767918907869112593870878204145615928290375086195098919355531430003571366638390993296583488184959318678321571278510231561645872308920917404996519309473979203661442792048291421574603018835698487725981963573816645574675640357569465990665689618997534740389987351864738104038598104713275375385003471306823348792559733332094774873827383320058176803218213042061965933143968710199376164960850951030741280074168795136
#6635663565033382363211849843446648120305449056573116171933923595209656581213410699649926913276685818674688954045817246263487415328838542489103709103428412175252447323358040041217431171817865818374522191881448865227314554997131690963910348820833080760482835650538394814181656599175839964284713498394589419605748581347163389157651739759144560719049281761889094518791244702056048080280278984031050608249265997808217512349309696532160108250480622956599732443714546043439089844571655280770141647694859907985919056009576606333143546094941635324929407538860140272562570973340199814409134962729885962133342668270226853146819

这个代码是将m右移315位然后左移315位。相当于把最低位的315位置为0

1	print((m>>315)<<315)

m是一个随机数乘以208加上flag得到的

1	m = bytes_to_long(long_to_bytes(randint(0,30))*208+flag)

c是$c=m^3\bmod n$

1	c = pow(m,3,n)

已知m高位，用CopperSmith已知明文高位攻击

当$|x|\leq N^{\frac{1}{e}}$,其中$m=mbar+x$时，下列关于x的方程

$$
c=m^e\bmod n =(mbar + x)^e \bmod n
$$

其中$mbar=(m>>kbits)<<kbits$

有解

首先我们验证下，条件是否满足；x是315位的$N^{\frac{1}{e}}$约有683，条件成立

所以显然对于已知明文高位的攻击，还需要e比较小这个条件，不然e=65537明显解不出来

1	f = (mbar + x) ^ e - c

这是解出来的代码

from Crypto.Util.number import *

n = 14113948189208713011909396304970377626324044633561155020366406284451614054260708934598840781397326960921718892801653205159753091559901114082556464576477585198060530094478860626532455065960136263963965819002575418616768412539016154873800614138683106056209070597212668250136909436974469812231498651367459717175769611385545792201291192023843434476550550829737236225181770896867698281325858412643953550465132756142888893550007041167700300621499970661661288422834479368072744930285128061160879720771910458653611076539210357701565156322144818787619821653007453741709031635862923191561438148729294430924288173571196757351837
mbar = 1520800285708753284739523608878585974609134243280728660335545667177630830064371336150456537012842986526527904043383436211487979254140749228004148347597566264500276581990635110200009305900689510908049771218073767918907869112593870878204145615928290375086195098919355531430003571366638390993296583488184959318678321571278510231561645872308920917404996519309473979203661442792048291421574603018835698487725981963573816645574675640357569465990665689618997534740389987351864738104038598104713275375385003471306823348792559733332094774873827383320058176803218213042061965933143968710199376164960850951030741280074168795136
c = 6635663565033382363211849843446648120305449056573116171933923595209656581213410699649926913276685818674688954045817246263487415328838542489103709103428412175252447323358040041217431171817865818374522191881448865227314554997131690963910348820833080760482835650538394814181656599175839964284713498394589419605748581347163389157651739759144560719049281761889094518791244702056048080280278984031050608249265997808217512349309696532160108250480622956599732443714546043439089844571655280770141647694859907985919056009576606333143546094941635324929407538860140272562570973340199814409134962729885962133342668270226853146819
e = 3
kbits = 315

PR.<x>=PolynomialRing(Zmod(n))
f = (mbar + x) ^ e - c
x0 = f.small_roots(X=2^kbits, beta=1)[0]  # find root < 2^kbits with factor = n

print(long_to_bytes(mbar + x0))

2 CopperSmith已知明文高位攻击

觉得这个高位攻击很有意思，但是没有博客能把这个部分讲的很详细，于是找了点资料看了一下。

看了一下发现并不简单，这里简单说一下，专门写一个博客讲解这部分内容，其中涉及到了格密码等问题。

首先我们知道$c_1\equiv m_1\bmod N$,并且$m_1 \equiv f(m_2)\bmod N$，那么我们可以知道m2是$f(x)^e\equiv c_1 \bmod N$的一个解，即它是方程$f(x)^e-c_1$在模N意义下的一个根。同样，m2是$x^e$模N意义下的一个根，所以x-m2同时除以以上两个多项式。因此我们可求得两个多项式的最大公因子，如果最大公因子恰好是线性的话，那么我们就求得了m2,在e很小的情况下，最大公因子一定是线性的。

当e=3且$f(x)=a*x+b$的情况下可求得m2