[原创] CTF2017 第10题海风月影cm 破解过程-CTF对抗-看雪-安全社区|安全招聘|kanxue.com

[原创] CTF2017 第10题海风月影cm 破解过程

2017-6-20 21:21 6139

[原创] CTF2017 第10题海风月影cm 破解过程

爱琴海

2017-6-20 21:21

6139

序言：

本题对于初学者的度在于准确识别算法流程，对RSA算法的深入理解和推理要求。

一、查壳，pe格式，64位无壳，初步运行看界面命令提示符，了解作品

二、分析算法流程

//动态跟一下流程：

000000013F946FA9 | 83 F8 46                  | cmp eax,46                                      | 注意长度70位
000000013F946FAC | 0F 85 FA 01 00 00         | jne <cm8.Failed>                                |
000000013F946FB2 | 45 33 C0                  | xor r8d,r8d                                     |
000000013F946FB5 | 41 8B D0                  | mov edx,r8d                                     |
000000013F946FB8 | 0F 1F 84 00 00 00 00 00   | nop dword ptr ds:[rax+rax]                      |
000000013F946FC0 | 0F B6 0C 1A               | movzx ecx,byte ptr ds:[rdx+rbx]                 | 读取input
000000013F946FC4 | 8D 41 D0                  | lea eax,dword ptr ds:[rcx-30]                   | 转数字
000000013F946FC7 | 3C 09                     | cmp al,9                                        | <=9 0-9
000000013F946FC9 | 76 0C                     | jbe cm8.13F946FD7                               |
000000013F946FCB | 80 E9 41                  | sub cl,41                                       |
000000013F946FCE | 80 F9 19                  | cmp cl,19                                       | <=Z A-Z
000000013F946FD1 | 0F 87 D5 01 00 00         | ja <cm8.Failed>                                 |
000000013F946FD7 | 48 FF C2                  | inc rdx                                         |
000000013F946FDA | 48 83 FA 46               | cmp rdx,46                                      |
000000013F946FDE | 7C E0                     | jl cm8.13F946FC0                                | >= 70位
000000013F946FE0 | 8B 05 3A AF 04 00         | mov eax,dword ptr ds:[13F991F20]                | 读取input
000000013F946FE6 | 89 05 AC BF 04 00         | mov dword ptr ds:[13F992F98],eax                | 13F992F98:"123456"
000000013F946FEC | 0F B7 05 31 AF 04 00      | movzx eax,word ptr ds:[13F991F24]               | 第1-6位:"123456" e
000000013F946FF3 | 48 89 7C 24 40            | mov qword ptr ss:[rsp+40],rdi                   | [rsp+40]:&"C:\\cm8.exe", rdi:"87118A460FFB1637E7AEBBB291FA09224753703AE484CF8477AEA77BCC44DF43"
000000013F946FF8 | 48 8D 3D 31 BF 04 00      | lea rdi,qword ptr ds:[13F992F30]                | rdi:"87118A460FFB1637E7AEBBB291FA09224753703AE484CF8477AEA77BCC44DF43", 13F992F30:"87118A460FFB1637E7AEBBB291FA09224753703AE484CF8477AEA77BCC44DF43"
000000013F946FFF | 66 89 05 96 BF 04 00      | mov word ptr ds:[13F992F9C],ax                  | 13F992F9C:"56"
000000013F947006 | 66 66 0F 1F 84 00 00 00 0 | nop word ptr ds:[rax+rax]                       |
000000013F947010 | 41 0F B6 44 18 06         | movzx eax,byte ptr ds:[r8+rbx+6]                | r8+rbx*1+6:"8A460FFB1637E7AEBBB291FA09224753703AE484CF8477AEA77BCC44DF43"
000000013F947016 | 41 88 04 38               | mov byte ptr ds:[r8+rdi],al                     | 第7-70位 p
000000013F94701A | 4D 8D 40 01               | lea r8,qword ptr ds:[r8+1]                      |
000000013F94701E | 84 C0                     | test al,al                                      |
000000013F947020 | 75 EE                     | jne cm8.13F947010                               |
000000013F947022 | 41 B8 10 00 00 00         | mov r8d,10                                      | 16
000000013F947028 | 48 8D 15 69 BF 04 00      | lea rdx,qword ptr ds:[13F992F98]                | e
000000013F94702F | 48 8D 0D DA AE 04 00      | lea rcx,qword ptr ds:[13F991F10]                |
000000013F947036 | E8 55 09 00 00            | call <cm8.turntohex>                            | 字符转为十六进制
000000013F94703B | 41 B8 10 00 00 00         | mov r8d,10                                      | 16
000000013F947041 | 48 8D 0D D8 BE 04 00      | lea rcx,qword ptr ds:[13F992F20]                | p
000000013F947048 | 48 8B D7                  | mov rdx,rdi                                     | rdi:"87118A460FFB1637E7AEBBB291FA09224753703AE484CF8477AEA77BCC44DF43"
000000013F94704B | E8 40 09 00 00            | call <cm8.turntohex>                            | 字符转为十六进制
000000013F947050 | BA F4 01 00 00            | mov edx,1F4                                     |
000000013F947055 | 48 8D 0D C4 BE 04 00      | lea rcx,qword ptr ds:[13F992F20]                | p 素数
000000013F94705C | E8 EF 02 00 00            | call <cm8.prime>                                |
000000013F947061 | 48 8B 7C 24 40            | mov rdi,qword ptr ss:[rsp+40]                   | rdi:"87118A460FFB1637E7AEBBB291FA09224753703AE484CF8477AEA77BCC44DF43", [rsp+40]:&"C:\\cm8.exe"
000000013F947066 | 85 C0                     | test eax,eax                                    |
000000013F947068 | 0F 84 3E 01 00 00         | je <cm8.Failed>                                 |
000000013F94706E | BA F4 01 00 00            | mov edx,1F4                                     |
000000013F947073 | 48 8D 0D 96 AE 04 00      | lea rcx,qword ptr ds:[13F991F10]                | e 素数
000000013F94707A | E8 D1 02 00 00            | call <cm8.prime>                                |
000000013F94707F | 85 C0                     | test eax,eax                                    |
000000013F947081 | 0F 84 25 01 00 00         | je <cm8.Failed>                                 |
000000013F947087 | 33 D2                     | xor edx,edx                                     |
000000013F947089 | 48 8D 0D 60 AE 04 00      | lea rcx,qword ptr ds:[13F991EF0]                |
000000013F947090 | E8 3B 0A 00 00            | call <cm8.init>                                 |
000000013F947095 | 41 B8 10 00 00 00         | mov r8d,10                                      |
000000013F94709B | 48 8D 15 9E 4E 04 00      | lea rdx,qword ptr ds:[13F98BF40]                | 13F98BF40:"6248BC3AB92A33B000FDB88568F19727F92F79EB68FF6AD73203EFD20A3E331BE941C7AA288095F33BC4B255FD983114D480EFFBEE2E313E6218A57F9CCC8189"
000000013F9470A2 | 48 8D 0D 37 AE 04 00      | lea rcx,qword ptr ds:[13F991EE0]                |
000000013F9470A9 | E8 E2 08 00 00            | call <cm8.turntohex>                            | n
000000013F9470AE | 41 B8 10 00 00 00         | mov r8d,10                                      |
000000013F9470B4 | 48 8D 15 15 4F 04 00      | lea rdx,qword ptr ds:[13F98BFD0]                | 13F98BFD0:"2476A7F02588913F228923E1F36F963F29708C07B117396817A6B94C336FC77FF7D381925EB40CFED8FBE894570155E41569B4EC69B26CB0320105A29651CB4B"
000000013F9470BB | 48 8D 0D 3E AE 04 00      | lea rcx,qword ptr ds:[13F991F00]                |
000000013F9470C2 | E8 C9 08 00 00            | call <cm8.turntohex>                            | D
000000013F9470C7 | 33 D2                     | xor edx,edx                                     |
000000013F9470C9 | 48 8D 4C 24 20            | lea rcx,qword ptr ss:[rsp+20]                   |
000000013F9470CE | E8 FD 09 00 00            | call <cm8.init>                                 |
000000013F9470D3 | 4C 8D 05 46 BE 04 00      | lea r8,qword ptr ds:[13F992F20]                 | p
000000013F9470DA | 48 8D 15 FF AD 04 00      | lea rdx,qword ptr ds:[13F991EE0]                | n
000000013F9470E1 | 48 8D 4C 24 20            | lea rcx,qword ptr ss:[rsp+20]                   |
000000013F9470E6 | E8 25 0A 00 00            | call <cm8.mod>                                  | n % p
000000013F9470EB | 33 D2                     | xor edx,edx                                     |
000000013F9470ED | 48 8D 4C 24 20            | lea rcx,qword ptr ss:[rsp+20]                   |
000000013F9470F2 | E8 D9 04 00 00            | call cm8.13F9475D0                              | n % p == 0
000000013F9470F7 | 85 C0                     | test eax,eax                                    |
000000013F9470F9 | 0F 85 AD 00 00 00         | jne <cm8.Failed>                                |
000000013F9470FF | 4C 8D 05 1A BE 04 00      | lea r8,qword ptr ds:[13F992F20]                 | p
000000013F947106 | 48 8D 15 D3 AD 04 00      | lea rdx,qword ptr ds:[13F991EE0]                | n
000000013F94710D | 48 8D 0D DC AD 04 00      | lea rcx,qword ptr ds:[13F991EF0]                |
000000013F947114 | E8 C7 00 00 00            | call <cm8.div>                                  | q = n/p
000000013F947119 | 48 8D 15 D0 AD 04 00      | lea rdx,qword ptr ds:[13F991EF0]                |
000000013F947120 | 48 8D 0D F9 BD 04 00      | lea rcx,qword ptr ds:[13F992F20]                |
000000013F947127 | E8 34 04 00 00            | call cm8.13F947560                              | q >= p
000000013F94712C | 85 C0                     | test eax,eax                                    |
000000013F94712E | 7F 7C                     | jg <cm8.Failed>                                 |
000000013F947130 | 41 B8 01 00 00 00         | mov r8d,1                                       |
000000013F947136 | 48 8D 15 E3 BD 04 00      | lea rdx,qword ptr ds:[13F992F20]                | p
000000013F94713D | 48 8D 0D DC BD 04 00      | lea rcx,qword ptr ds:[13F992F20]                |
000000013F947144 | E8 A7 08 00 00            | call <cm8.sub>                                  | p-1
000000013F947149 | 41 B8 01 00 00 00         | mov r8d,1                                       |
000000013F94714F | 48 8D 15 9A AD 04 00      | lea rdx,qword ptr ds:[13F991EF0]                | q
000000013F947156 | 48 8D 0D 93 AD 04 00      | lea rcx,qword ptr ds:[13F991EF0]                |
000000013F94715D | E8 8E 08 00 00            | call <cm8.sub>                                  | q-1
000000013F947162 | 4C 8D 05 87 AD 04 00      | lea r8,qword ptr ds:[13F991EF0]                 |
000000013F947169 | 48 8D 15 B0 BD 04 00      | lea rdx,qword ptr ds:[13F992F20]                |
000000013F947170 | 48 8D 4C 24 20            | lea rcx,qword ptr ss:[rsp+20]                   | M = (b-1) * (q-1)
000000013F947175 | E8 96 04 00 00            | call <cm8.mul>                                  |
000000013F94717A | 4C 8D 44 24 20            | lea r8,qword ptr ss:[rsp+20]                    |
000000013F94717F | 48 8D 15 8A AD 04 00      | lea rdx,qword ptr ds:[13F991F10]                |
000000013F947186 | 48 8D 4C 24 20            | lea rcx,qword ptr ss:[rsp+20]                   |
000000013F94718B | E8 20 02 00 00            | call <cm8.calc_D>                               | D = (K * M + 1) / e
000000013F947190 | 48 8D 54 24 20            | lea rdx,qword ptr ss:[rsp+20]                   | D
000000013F947195 | 48 8D 0D 64 AD 04 00      | lea rcx,qword ptr ds:[13F991F00]                | D
000000013F94719C | E8 BF 03 00 00            | call cm8.13F947560                              | 求D
000000013F9471A1 | 48 8D 0D D8 4C 04 00      | lea rcx,qword ptr ds:[13F98BE80]                |
000000013F9471A8 | 85 C0                     | test eax,eax                                    |
000000013F9471AA | 74 07                     | je cm8.13F9471B3                                |
000000013F9471AC | 48 8D 0D B5 4C 04 00      | lea rcx,qword ptr ds:[13F98BE68]                |
000000013F9471B3 | E8 E8 FC FF FF            | call <cm8.print>                                |
000000013F9471B8 | 48 8D 0D B5 4C 04 00      | lea rcx,qword ptr ds:[13F98BE74]                | 13F98BE74:"pause"
000000013F9471BF | E8 F0 5F 02 00            | call cm8.13F96D1B4                              |
000000013F9471C4 | 33 C0                     | xor eax,eax                                     |
000000013F9471C6 | 48 83 C4 30               | add rsp,30                                      | rsp:&"12345687118A460FFB1637E7AEBBB291FA09224753703AE484CF8477AEA77BCC44DF43"
000000013F9471CA | 5B                        | pop rbx                                         | rbx:"12345687118A460FFB1637E7AEBBB291FA09224753703AE484CF8477AEA77BCC44DF43"
000000013F9471CB | C3                        | ret                                             |

//IDA:

__int64 sub_6F50()
{
  signed __int64 v0; // rax@1
  __int64 v1; // r8@4
  signed __int64 v2; // rdx@4
  char v3; // cl@5
  char v4; // al@9
  int v5; // eax@14
  __int64 v6; // rcx@14
  char v8; // [sp+20h] [bp-18h]@12

  sub_6EA0("=========================================================================\n");
  sub_6EA0("                     看雪CTF2017 CrackMe by 海风月影\n\n");
  sub_6EA0(&unk_4BF18);
  sub_6F00(&unk_4BF2C, &dword_51F20);
  sub_6EA0(&unk_4BF30);
  v0 = -1i64;
  do
    ++v0;
  while ( *((_BYTE *)&dword_51F20 + v0) );
  if ( (_DWORD)v0 == 70 )
  {
    v1 = 0i64;
    v2 = 0i64;
    while ( 1 )
    {
      v3 = *((_BYTE *)&dword_51F20 + v2);
      if ( (unsigned __int8)(v3 - 48) > 9u && (unsigned __int8)(v3 - 65) > 0x19u )
        break;
      ++v2;
      if ( v2 >= 70 )
      {
        dword_52F98 = dword_51F20;
        word_52F9C = word_51F24;
        do
        {
          v4 = *((_BYTE *)&dword_51F20 + v1 + 6);
          byte_52F30[v1++] = v4;
        }
        while ( v4 );
        turntohex((__int64)&unk_51F10, (__int64)&dword_52F98, 0x10u);// e (input_1-6)
        turntohex((__int64)&unk_52F20, (__int64)byte_52F30, 0x10u);// p (input_7-70)
        if ( isprime((__int64)&unk_52F20, 0x1F4u) )
        {
          if ( isprime((__int64)&unk_51F10, 0x1F4u) )
          {
            init_7AD0((__int64)&unk_51EF0, 0i64);
            turntohex(
              (__int64)&unk_51EE0,              // n
              (__int64)"6248BC3AB92A33B000FDB88568F19727F92F79EB68FF6AD73203EFD20A3E331BE941C7AA288095F33BC4B255FD983114D480EFFBEE2E313E6218A57F9CCC8189",
              0x10u);
            turntohex(
              (__int64)&unk_51F00,              // D_dest
              (__int64)"2476A7F02588913F228923E1F36F963F29708C07B117396817A6B94C336FC77FF7D381925EB40CFED8FBE894570155E41569B4EC69B26CB0320105A29651CB4B",
              0x10u);
            init_7AD0((__int64)&v8, 0i64);
            mod_7B10((__int64)&v8, (__int64)&unk_51EE0, (__int64)&unk_52F20);// n % p
            if ( !cmp_75D0(&v8, 0i64) )         // n % p == 0
            {
              div_71E0(&unk_51EF0, &unk_51EE0, &unk_52F20);// q = n / p
              if ( (signed int)cmp_7560((__int64)&unk_52F20, (__int64)&unk_51EF0) <= 0 )// p >= q
              {
                sub_79F0((__int64)&unk_52F20, (__int64)&unk_52F20, 1ui64);// p-1
                sub_79F0((__int64)&unk_51EF0, (__int64)&unk_51EF0, 1ui64);// q-1
                mul_7610((__int64)&v8, (__int64)&unk_52F20, (__int64)&unk_51EF0);// *  M=(P-1)*(Q-1)
                calc_d_73B0((__int64)&v8, (__int64)&unk_51F10, (__int64)&v8);// D = (K*M+1)/e
                v5 = cmp_7560((__int64)&unk_51F00, (__int64)&v8);// D == D_dest
                v6 = (__int64)"注册成功!!!\n\n";
                if ( !v5 )
                  goto LABEL_16;
              }
            }
          }
        }
        break;
      }
    }
  }
  v6 = (__int64)"注册失败\n\n";
LABEL_16:
  sub_6EA0(v6);
  sub_2D1B4("pause");
  return 0i64;
}

//整理算法，这是典型的RSA算法，作者给出D、N，要求e为素数，限制了e的长度，并且要求q>=p，防止多解，要求攻击者找到e和p

e = 6位质数，穷举吧
p = 64位质数
q = 质数，且 q >= p
M = (p-1)*(q-1)
N = p*q = 6248BC3AB92A33B000FDB88568F19727F92F79EB68FF6AD73203EFD20A3E331BE941C7AA288095F33BC4B255FD983114D480EFFBEE2E313E6218A57F9CCC8189
D = 2476A7F02588913F228923E1F36F963F29708C07B117396817A6B94C336FC77FF7D381925EB40CFED8FBE894570155E41569B4EC69B26CB0320105A29651CB4B
e 与 M 互质，只有1这个公约数
k = 倍数
D 满足：e*D-1 = k*(p-1)*(q-1)

三、算法破解

㈠、尝试分解N，短时间内搞不定，换种思路
㈡、先找到e——筛选6位质数e，首先根据k被整除、e与M的互质，筛选出可能的公钥e，再用D解密RSA，用e加密RSA，进一步找到准确e，极大提高速度

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# Ctf.pediy.com ctf2017 crackme 10 keygen
# python 3.6.0 32bit
# written by 爱琴海
# 2017/06/20

import math
import time
import pickle
import os

def Main():
    start_time = time.clock()
    dict = []
    # 准备创建和加载6位素数e进行穷举，判断素数的代码网上拷贝的，效率一般
    if os.path.exists('cm10.pkl') == True:
        print('发现本地素数文件，正在加载......')
        Caihongbiao = open('cm10.pkl', 'rb')
        dict = pickle.load(Caihongbiao)
        Caihongbiao.close()
        print('本地数据加载完成!')
    else:
        print('本地不存在素数数据，重新生成请等待......')
        n = 0
        #只检测奇数，偶数能被2除
        for e in range(0x100001,0x1000000,0x2): 
            if prime(e):
                dict.append(e)
                n += 1
        # 保存本地，下次待用
        Caihongbiao = open('cm10.pkl', 'wb')
        pickle.dump(dict, Caihongbiao)
        Caihongbiao.close()
        print('建立素数文件完成，用时: %.3f 秒' % (time.clock() - start_time))
    print('初始化六位素数用时: %.3f 秒' % (time.clock() - start_time))
    print('六位素数个数:', len(dict))
    print('开始计算公钥......')

    # 定义RSA的私钥D，模数N，假设密文C
    D = 0x2476A7F02588913F228923E1F36F963F29708C07B117396817A6B94C336FC77FF7D381925EB40CFED8FBE894570155E41569B4EC69B26CB0320105A29651CB4B
    N = 0x6248BC3AB92A33B000FDB88568F19727F92F79EB68FF6AD73203EFD20A3E331BE941C7AA288095F33BC4B255FD983114D480EFFBEE2E313E6218A57F9CCC8189
    #在筛选出来的e中进行准确匹配
    C = 0x123456
    # 使用私钥解密C，解密结果用来校验公钥e是否正确
    Check_decrypt = quick_ming_mod(C, D, N)
    #print('测试RSA解密数据: %x' % Check_decrypt)

    # 开始计算e
    start_time = time.clock()
    for e1 in range(len(dict)-1,-1,-1):
    #for e1 in range(0,len(dict)):
        # 最开始穷举从0开始，也可以倒序
        M_k = (dict[e1] * D - 1)
        # 先筛选出所有可能的k
        k = M_k // N + 1
        # k必须能被(e*D-1)整除
        if M_k % k == 0:
            M = M_k // k
            # 求出M
            if gcd(M,dict[e1]) == 0x1:
            # e与M互质                
                #print('找到可能的公钥e:',('%x'%dict[e1]).upper())
                #print('找到可能的倍数k:',('%x'%k).upper())
                if quick_ming_mod(Check_decrypt,dict[e1],N) == C:
                    p_add_q = N - M + 1
                    print ('找到准确的公钥e:',('%x'%dict[e1]).upper())
                    print ('p + q =',('%x'%p_add_q).upper())
                    print ('p * q =',('%x'%N).upper())
                    break
                    
    print('破解RSA用时: %.3f 秒,接下来请手工完成解方程' % (time.clock() - start_time))

    return

#检查互质
def gcd(a,b):  
    if a%b == 0:  
        return b  
    else :  
        return gcd(b,a%b) 

#检查素数
def prime(n):  
    if n%2 == 0:  
        return n==2  
    if n%3 == 0:  
        return n==3  
    if n%5 == 0:  
        return n==5  
    #只考虑奇数作为可能因子  
    for p in range(7,int(math.sqrt(n))+1,2): 
        if n%p == 0:  
            return 0  
    return 1

#二分法冥取模算法
def quick_ming_mod(di,ming,mode):
    temp=0x1
    di_1=di
    if ming>0x0 and di>0x0:
        while ming>0x0:
            if ming&0x1:
                temp=temp*di_1%mode
                ming=ming-1
            else:
                di_1=(di_1*di_1)%mode
                ming=ming>>0x1
    elif di>0x0:
        temp=0x1
    else:
        temp=0x0
    return temp

if __name__=="__main__":
    Main()

C:\python_int>python cm10.py
  发现本地素数文件，正在加载......
  本地数据加载完成!
  初始化六位素数用时: 0.087 秒
  六位素数个数: 995846
  开始计算公钥......
  找到准确的公钥e: F552B3
  p + q = 13F40BC9DA5C21AE87DD77A150D9FECA2B17B4A84DB1108FE9D4DDA6A9C7D9086
  p * q = 6248BC3AB92A33B000FDB88568F19727F92F79EB68FF6AD73203EFD20A3E331BE941C7AA288095F33BC4B255FD983114D480EFFBEE2E313E6218A57F9CCC8189
  破解RSA用时: 0.065 秒,接下来请手工完成解方程

  1、6位质数e，一共995846个
  2、穷举到e：F552B3

㈢、根据D的条件找到M

  1、e * D - 1 = 22F156399644A2FE6FD5746AA070C1BF98F22609E8DB54343F1DEB46DB32BBB287A94709791DFE53F460C7FE9A67DE76BA9B80FB1E62EB13324A31AF1EE11CDD162B70
  2、(e * D - 1) / N = 5B03DB-->M略比N小，所以k需要从（5B03DB + 1）开始穷举，满足被 e*D-1 整除的最小K即可，秒出K：5B03DC
  3、M = (e * D - 1) / k = 6248BC3AB92A33B000FDB88568F19727F92F79EB68FF6AD73203EFD20A3E331AAA010B0C82BE7B0ABDED3840EFF844722305A577131D283FC4CACB15004EF104

㈣、已知p、q为素数，q >= p，已知n，上文也已经求出 M

  1、p * q = 6248BC3AB92A33B000FDB88568F19727F92F79EB68FF6AD73203EFD20A3E331BE941C7AA288095F33BC4B255FD983114D480EFFBEE2E313E6218A57F9CCC8189
  2、(p - 1) * (q - 1) = 6248BC3AB92A33B000FDB88568F19727F92F79EB68FF6AD73203EFD20A3E331AAA010B0C82BE7B0ABDED3840EFF844722305A577131D283FC4CACB15004EF104
  3、等式2转换为 p * q - (p + q - 1) = 6248BC3AB92A33B000FDB88568F19727F92F79EB68FF6AD73203EFD20A3E331AAA010B0C82BE7B0ABDED3840EFF844722305A577131D283FC4CACB15004EF104
  4、把等式1带入等式3，得到 p + q = 13F40BC9DA5C21AE87DD77A150D9FECA2B17B4A84DB1108FE9D4DDA6A9C7D9086
  5、根据等式1和等式4，解方程，又因为 q >= p 得到：
     p = 8DBDDE72E2E693B2AED5C769C0DCB3DA83534480A80E652FFE53544CD91A18C3
     q = B182DE2AC2DB8735CF01B2AB4CC338C82E2806043302A3CE9EFA861DC36377C3

㈤、整理答案

  e 连接 p = F552B38DBDDE72E2E693B2AED5C769C0DCB3DA83534480A80E652FFE53544CD91A18C3

四、总结

RSA算法需要谨慎选择密钥，最好不要颠倒公钥和私钥，这大概是本题作者给大家的科普启示吧！

[培训]《安卓高级研修班(网课)》月薪三万计划，掌握调试、分析还原ollvm、vmp的方法，定制art虚拟机自动化脱壳的方法

上传的附件：

cm10.rar （153.60kb，29次下载）

收藏・3

点赞・1

打赏

最新回复 (6)
Spoorer 雪币： 23 活跃值： (10) 能力值： ( LV2，RANK：10 ) 在线值：发帖 0 回帖 3 粉丝 0 关注私信	Spoorer 2017-6-29 01:19 2 楼 0
weihuolee 雪币： 0 活跃值： (239) 能力值： ( LV2，RANK：10 ) 在线值：发帖 0 回帖 6 粉丝 0 关注私信	weihuolee 2017-6-29 07:27 3 楼 0
foolishx 雪币： 156 活跃值： (150) 能力值： ( LV2，RANK：10 ) 在线值：发帖 4 回帖 42 粉丝 3 关注私信	foolishx 2017-10-10 15:04 4 楼 0 高！
wx_心隐草雪币： 5 活跃值： (10) 能力值： ( LV2，RANK：10 ) 在线值：发帖 0 回帖 6 粉丝 0 关注私信	wx_心隐草 2017-10-20 23:32 5 楼 0 2、(e * D - 1) / N = 5B03DB-->M略比N小，所以k需要从（5B03DB + 1）开始穷举，满足被 e*D-1 整除的最小K即可，秒出K：5B03DC 这一句没看懂，K值的最小值是根据什么原理得出的？
爱琴海雪币： 1355 活跃值： (329) 能力值： ( LV13，RANK：920 ) 在线值：发帖 70 回帖 633 粉丝 7 关注私信	爱琴海 13 2017-10-20 23:51 6 楼 0 wx_心隐草 2、(e * D - 1) / N = 5B03DB-->M略比N小，所以k需要从（5B03DB + 1）开始穷举，满足被 eD-1 整除的最小K即可，秒出K：5B03DC 这一句没看懂，K ... M = (p-1)(q-1) N = pq 两者相差很小，推理(eD－1)/N与(e*D－1)/M结果极为接近，由此可以推测相邻最小满足公式的就是k值。你也可以对表达式展开求极限看看。
wx_心隐草雪币： 5 活跃值： (10) 能力值： ( LV2，RANK：10 ) 在线值：发帖 0 回帖 6 粉丝 0 关注私信	wx_心隐草 2017-11-2 13:01 7 楼 0 谢谢！
	游客登录 \| 注册方可回帖　回帖　表情雪币赚取及消费高级回复

爱琴海

发帖

633

回帖

920

RANK

关注

私信

他的文章

#18周年# 逆向的天马行空

[原创] 看雪.TSRC 2017CTF秋季赛第三题crackMe破解过程

[原创] 看雪.TSRC 2017CTF秋季赛第二题——只缘身在此山中，不识庐山真面目

[原创] 第一题 Helllo-CTF 破解记录

[注意] 2017 最新 CTF Demo 试玩版题目，不用等了快来吧

关于我们

联系我们

企业服务

看雪公众号

最新回复 (6)
Spoorer 雪币： 23 活跃值： (10) 能力值： ( LV2，RANK：10 ) 在线值：发帖 0 回帖 3 粉丝 0 关注私信	Spoorer 2017-6-29 01:19 2 楼 0
weihuolee 雪币： 0 活跃值： (239) 能力值： ( LV2，RANK：10 ) 在线值：发帖 0 回帖 6 粉丝 0 关注私信	weihuolee 2017-6-29 07:27 3 楼 0
foolishx 雪币： 156 活跃值： (150) 能力值： ( LV2，RANK：10 ) 在线值：发帖 4 回帖 42 粉丝 3 关注私信	foolishx 2017-10-10 15:04 4 楼 0 高！
wx_心隐草雪币： 5 活跃值： (10) 能力值： ( LV2，RANK：10 ) 在线值：发帖 0 回帖 6 粉丝 0 关注私信	wx_心隐草 2017-10-20 23:32 5 楼 0 2、(e * D - 1) / N = 5B03DB-->M略比N小，所以k需要从（5B03DB + 1）开始穷举，满足被 e*D-1 整除的最小K即可，秒出K：5B03DC 这一句没看懂，K值的最小值是根据什么原理得出的？
爱琴海雪币： 1355 活跃值： (329) 能力值： ( LV13，RANK：920 ) 在线值：发帖 70 回帖 633 粉丝 7 关注私信	爱琴海 13 2017-10-20 23:51 6 楼 0 wx_心隐草 2、(e * D - 1) / N = 5B03DB-->M略比N小，所以k需要从（5B03DB + 1）开始穷举，满足被 eD-1 整除的最小K即可，秒出K：5B03DC 这一句没看懂，K ... M = (p-1)(q-1) N = pq 两者相差很小，推理(eD－1)/N与(e*D－1)/M结果极为接近，由此可以推测相邻最小满足公式的就是k值。你也可以对表达式展开求极限看看。
wx_心隐草雪币： 5 活跃值： (10) 能力值： ( LV2，RANK：10 ) 在线值：发帖 0 回帖 6 粉丝 0 关注私信	wx_心隐草 2017-11-2 13:01 7 楼 0 谢谢！
	游客登录 \| 注册方可回帖　回帖　表情雪币赚取及消费高级回复

[原创] CTF2017 第10题 海风月影cm 破解过程

[原创] CTF2017 第10题海风月影cm 破解过程