来源于一位师傅发的RSA的题目，这题正解是套公式，但是其实可以直接分解n。
题来康康别的师傅发给我的江西省赛的cry题，发现自己还是能很好的运用一些小技巧的，正解虽然不用分解n，但是咱还是可以分解n的hhh
题目分析
1
2
3
4
| n=27552304606229034903366058815849954030287648695063385362955432137790872571412035824128918674719247737295565001575991597519270789776408208970323808016733976338433371328100880898942106515627607388226912870981180215883273805491209461671730377099185278711453949265641966582563910708529619185885928310168288810488784242368160743359666583499117949407921812317700250240067929572558785431071173411100434109661677786734923283679392823901052633992456780285091988542875991410528415886437666510014123352497264017734716859350294159440761760921548702546470902740121962033241003215821780125194400741190925169397917247376657863011603
e=65537
c=8643831704675414121804983915084443744489969712473300784256427784417167322852556975560503484179280700293119974607254037642425650493676448134024809335297135239994950178868535219541095694358323044214971760829173918774094415933808417722001811285178546917655837402000771685507972240389565704149610032767242977174132826100177368764169367458684152505611469248099487912367364804360878611296860803835816266114046682291529593099394952245852157119233687981777202751472502060481232341206366584532964027749320641690448228420342308891797513656897566100268729012788419021059054907653832828437666012596894150751431936476816983845357
p-q=3216514606297172806828066063738105740383963382396892688569683235383985567043193404185955880509592930874764682428425994713750665248099953457550673860782324431970917492727256948066013701406000049963109681898567026552657377599263519201715733179565306750754520746601394738797021362510415215113118083969304423858
|
题目给了n和密文，还给了p和q的关系式，但是n是600多位十进制数直接分解不太现实，即便确定了p和q的位数复杂度也不允许。而且它数据刚刚好，python无法直接表示，所以我们就很难用python写这个分解n的脚本。这里有一个很好用的东西：java大数，java大数是字符串封装的可以运算的数，那么我们就可以通过这个很好的运算了。
既然直接分析不可行的话那么采取其它策略——爆破
编写脚本
思想是确定p的位数，然后q=p+x，从高位枚举，直到p*(p+x)刚好<n确定这一位数，就算p是300多位，每位枚举10中情况复杂度也不算高，那么这个就用java写脚本爆破了。
首先确定一下p的位数，这个很难简单，直接随便取若干位数为p，再算(p+x)*p与n相除，若得出来的值不超过10那基本就是这么多位数了，这里算出来位数是310位
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| import java.util.Scanner;
import java.math.*;
public class bignumber{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
BigInteger n = new BigInteger("27552304606229034903366058815849954030287648695063385362955432137790872571412035824128918674719247737295565001575991597519270789776408208970323808016733976338433371328100880898942106515627607388226912870981180215883273805491209461671730377099185278711453949265641966582563910708529619185885928310168288810488784242368160743359666583499117949407921812317700250240067929572558785431071173411100434109661677786734923283679392823901052633992456780285091988542875991410528415886437666510014123352497264017734716859350294159440761760921548702546470902740121962033241003215821780125194400741190925169397917247376657863011603");
BigInteger x = new BigInteger("3216514606297172806828066063738105740383963382396892688569683235383985567043193404185955880509592930874764682428425994713750665248099953457550673860782324431970917492727256948066013701406000049963109681898567026552657377599263519201715733179565306750754520746601394738797021362510415215113118083969304423858");
BigInteger i = new BigInteger("0");
for(int j=310;j>=1;j--) {
String s="1";
for(int k=0;k<j-1;k++) {
s+='0';
}
BigInteger pow=new BigInteger(s);
int bit=10;
BigInteger p=new BigInteger("0");
do {
bit--;
BigInteger m=pow.multiply(new BigInteger(Integer.toString(bit)));
BigInteger a=m.add(i);
p=a.multiply(a.add(x));
}while(n.compareTo(p)==-1);
i=i.add(pow.multiply(new BigInteger(Integer.toString(bit))));
System.out.println(i);
}
}
}
|
很容易就爆破出来了，最终得到
1
| p=164388402596326998398734266483348689718634308613134769513823133531277866932924580863368129180110157251658299906566819446945741582875064595447688991363818514760290461718304500609014489162133123761201603375706506435381197548902899274601380329856241471126508515906897368912158915277705061990280370468267906281833
|
解密脚本:
1
2
3
4
5
6
7
8
9
10
11
12
13
| from Crypto.Util.number import *
n=27552304606229034903366058815849954030287648695063385362955432137790872571412035824128918674719247737295565001575991597519270789776408208970323808016733976338433371328100880898942106515627607388226912870981180215883273805491209461671730377099185278711453949265641966582563910708529619185885928310168288810488784242368160743359666583499117949407921812317700250240067929572558785431071173411100434109661677786734923283679392823901052633992456780285091988542875991410528415886437666510014123352497264017734716859350294159440761760921548702546470902740121962033241003215821780125194400741190925169397917247376657863011603
p=164388402596326998398734266483348689718634308613134769513823133531277866932924580863368129180110157251658299906566819446945741582875064595447688991363818514760290461718304500609014489162133123761201603375706506435381197548902899274601380329856241471126508515906897368912158915277705061990280370468267906281833
e=65537
c=8643831704675414121804983915084443744489969712473300784256427784417167322852556975560503484179280700293119974607254037642425650493676448134024809335297135239994950178868535219541095694358323044214971760829173918774094415933808417722001811285178546917655837402000771685507972240389565704149610032767242977174132826100177368764169367458684152505611469248099487912367364804360878611296860803835816266114046682291529593099394952245852157119233687981777202751472502060481232341206366584532964027749320641690448228420342308891797513656897566100268729012788419021059054907653832828437666012596894150751431936476816983845357
x=3216514606297172806828066063738105740383963382396892688569683235383985567043193404185955880509592930874764682428425994713750665248099953457550673860782324431970917492727256948066013701406000049963109681898567026552657377599263519201715733179565306750754520746601394738797021362510415215113118083969304423858
q=p+x
d=inverse(e,(p-1)*(q-1))
m=pow(c,d,n)
flag=long_to_bytes(m)
print(flag)
|
得到flag=flag{9c0532a253809f180747b6da334b438f}
