2021羊城杯Crypto公钥部分WriteUp

水了三题公钥的Crypto题，都是RSA的，而且都是和n的分解相关的

bigRSA·

题目给了两个n，然后后面是两个n对应的正常的两次加密，按照这个信息量很自然的就把n1和n2做一次gcd，发现是不互素的，所以可以分解两个n，然后求出d，再做两次解密得到m。

但是，在实际用Sage操作的时候发现直接用Sage的pow是有点问题的：

# 'SageMath version 9.1, Release Date: 2020-05-20'
print(pow(pow(123, e, n1), e*d2, n2) == pow(123, e, n1)) # False
print(pow(int(pow(123, e, n1)), e*d2, n2) == pow(123, e, n1)) # True

用py写的话则没事：

from Crypto.Util.number import *
from gmpy2 import invert, gcd

n1 = 103835296409081751860770535514746586815395898427260334325680313648369132661057840680823295512236948953370895568419721331170834557812541468309298819497267746892814583806423027167382825479157951365823085639078738847647634406841331307035593810712914545347201619004253602692127370265833092082543067153606828049061
n2 = 115383198584677147487556014336448310721853841168758012445634182814180314480501828927160071015197089456042472185850893847370481817325868824076245290735749717384769661698895000176441497242371873981353689607711146852891551491168528799814311992471449640014501858763495472267168224015665906627382490565507927272073
e = 65537
c = 60406168302768860804211220055708551816238816061772464557956985699400782163597251861675967909246187833328847989530950308053492202064477410641014045601986036822451416365957817685047102703301347664879870026582087365822433436251615243854347490600004857861059245403674349457345319269266645006969222744554974358264

p = gcd(n1, n2)
q1 = n1//p
q2 = n2//p
assert p*q1==n1 and p*q2==n2

phi1 = (p-1)*(q1-1)
phi2 = (p-1)*(q2-1)
d1 = invert(e, phi1)
d2 = invert(e, phi2)

m = pow(c, d2, n2)
m = pow(m, d1, n1)
flag = long_to_bytes(int(m))
print(flag)
#SangFor{qSccmm1WrgvIg2Uq_cZhmqNfEGTz2GV8}

RSA?·

首先p和q是256位的素数，直觉上是可以直接暴力分解的：

题目的提示是RSA，直接看代码的话很难看出和RSA有什么联系，可以先把loop转换成数学的形式，设：

$$M = \begin{bmatrix} x & y \\ Dy & x \\ \end{bmatrix} \\ v = (x, y)$$

那么loop在做的事其实是（这里中括号指的是取第一行）：

$$v*M^{e-1} = (M^e)[0]$$

看到$M^e$猜想是个矩阵的RSA，自己随便生成一些小数据再验证一下，发现都有：

$$M^\phi = M\ (mod\ n)$$

猜想成立。现在n可以分解，就是$\phi$知道，e知道，可以求出d；$(M^e)[0]$知道，如果可以求出$M^e\ (mod\ n)$的话，就可以像RSA那样用$(M^e)^d = M\ (mod\ n)$解密了。

根据观察，可以得到：

$$(M^x)[1][0] = D*(M^x)[0][1] \\ (M^x)[1][1] = (M^x)[0][0]$$

于是就可以求出$(M^e)[1][0]$和$(M^e)[1][1]$，即求出$M^e\ (mod\ n)$，脚本：

# sage
from Crypto.Util.number import *
from gmpy2 import invert, iroot

n = 13390709926509813526471364597371124446888078365567927211781799241724742352679484983709219580483800891886832613684875066109177882219522305348565532970795023
v = (5404548088049249951619519701935576492239293254135836357417714329205323074367876875480850741613547220698045360461761929952847796420174204143917852624050110, 2110372753170830610718226848526649992911771424441223687775304654852191999130502986109306355582366065947895295520226816523397652918227241733632791793362785)
a = 1762039418842677123086894939949574689744108610561557889235294034870342076452734215004689409493802437034960516295735815195656138656970901855976802991519141
D = (a*a)%n
e = 65537

p = 115718235064789220654263009993128325569382592506655305434488398268608329541037
q = 115718235064789220654263009993128324769382192706654302434478391267607309966379
assert p*q==n

def fastPow(M, x, n):
    if x==0:
        return identity_matrix(len(M.columns()))
    res = fastPow(M, x//2, n)
    if x%2 == 1:
        return res*res*M % n
    else:
        return res*res % n

phi = (p-1)*(q-1)
d = e.inverse_mod(phi)

M = matrix([[v[0], v[1]], [v[1]*D, v[0]]])
#m = M^d%n
m = fastPow(M, d, n)
Y = m[0][1]
print('Y = %s' % Y)

print(long_to_bytes(int(Y)))
# GWHT{pell_equation_is_very_interesting}

easyRSA·

这是道让人非常头疼的题… …当时其实前一晚就已经有思路了，想着第二天九点才结束，八点起来应该也搞得定吧，谁知道后来代码+运行搞了四个多小时。。。（不过感觉上是非预期解？）

题目的意思是，用了这样的一个keyGen生成密钥：

$$p = 2ga + 1 \\ q = 2gb + 1 \\ h = 2gab + a + b$$

p、q、h都是素数，其中g是“很大”的数，a、b是“很小的数”；整理一下可以得到：

$$n = pq = 4g^2ab+2g(a+b)+1 \\ \frac{n-1}{2} = 2g^2ab+g(a+b) \\ \frac{n-1}{4g^2} = ab+\frac{a+b}{2g} = ab+negl()$$

根据最后一条式子 + 实际代码测试，有：

$$\sqrt{\frac{n-1}{4ab}} \approx g$$

因为a、b是很小的，爆破a和b就可得到g，然后得到p、q，然后就是正常的RSA解密了，于是就有脚本：

from gmpy2 import iroot

# original
n = 84236796025318186855187782611491334781897277899439717384242559751095347166978304126358295609924321812851255222430530001043539925782811895605398187299748256080526691975084042025794113521587064616352833904856626744098904922117855866813505228134381046907659080078950018430266048447119221001098505107823645953039
gamma = 0.48

# gamma == 0.49
n = 25876225522890846556694449833494254540262333611158337123604777179863694236498355670851480908852313896681043771428258385755840617295126898560098248525302865459336697905788090823970968293147657498562477274750658646012858288861287729533422138185695389851242485849321943069495999658596606801403724051868563060097
gamma = 0.49

lbound = 2**(int(1024*(0.5-gamma))-1)
ubound = 2**int(1024*(0.5-gamma))
print(lbound, ubound)
for a in range(lbound, ubound):
    print(a)
    for b in range(lbound, ubound):
        g = int(iroot((n-1)//(4*a*b), 2)[0])
        p = 2*g*a+1
        q = 2*g*b+1
        if p*q==n:
            print('p = %s' % p)
            print('q = %s' % q)
            exit(0)

经验证，当gamma是0.49的时候脚本是起作用的，但，gamma是0.48（即题目给的）的时候，算了一下要一个星期（比赛才一天啊喂… …）；于是又搞了个C版本的，再算一下要两天… …；最后现学了一波C的多线程，才用了一顿饭+的时间搞了出来，最终代码：

//gcc get.c -lgmp -lm -lpthread -g && ./a.out
#include <stdio.h>
#include <stdlib.h>
#include <gmp.h>
#include <pthread.h>

#define NT 16

typedef struct {
  mpz_t* n;
  mpz_t* n_1_2;
  long ast;
  long aed;
}para;

void* run(void* arg) {
  para* par = (para*) arg;
  mpz_t* n = par->n; 
  mpz_t* n_1_2 = par->n_1_2;
  long ast = par->ast;
  long aed = par->aed;
  //printf("%ld, %ld\n", ast, aed);
  //pthread_exit(0);
  mpz_t g, p, q, n2;
  mpz_inits(g, p, q, n2, 0, NULL);
  for (long a=ast; a<aed; a++) {
    if (a%1000 == 0) {
      printf("%ld\n", a);
    }
    long a2 = 2*a;
    for (long b=524288; b<1048576; b++) {
      mpz_div_ui(g, *n_1_2, a2*b);
      mpz_sqrt(g, g);

      if(mpz_divisible_p(*n_1_2, g) == 1) {
        gmp_printf("g = %Zd\n", g);
        mpz_mul_ui(p, g, a2);
        mpz_add_ui(p, p, 1);
        mpz_mul_ui(q, g, 2*b);
        mpz_add_ui(q, q, 1);
        mpz_mul(n2, p, q);
        if(mpz_cmp(*n, n2) == 0) {
          printf("a = %ld\nb = %ld\n", a, b);
          gmp_printf("p = %Zd\nq = %Zd\n", p, q);
          mpz_clears(*n, *n_1_2, g, p, q, n2, NULL);
          exit(0);
        }
      }
    }
  }
  pthread_exit(0);
}

int main() {
  mpz_t n, n_1_2, g, p, q, n2;
  mpz_inits(n, n_1_2, g, p, q, n2, 0, NULL);
  mpz_init_set_str(n, "84236796025318186855187782611491334781897277899439717384242559751095347166978304126358295609924321812851255222430530001043539925782811895605398187299748256080526691975084042025794113521587064616352833904856626744098904922117855866813505228134381046907659080078950018430266048447119221001098505107823645953039", 10);
  mpz_sub_ui(n_1_2, n, 1);
  mpz_div_ui(n_1_2, n_1_2, 2);
  
  pthread_t tids[NT];
  para par[NT];
  long ub = 1048576;
  long lb = ub/2;
  long delta = lb/NT;
  for (int i=0; i<NT; i++) {
    par[i].n = &n;
    par[i].n_1_2 = &n_1_2;
    par[i].ast = lb+i*delta;
    par[i].aed = lb+(i+1)*delta;
    pthread_create(&tids[i], NULL, run, par+i);
  }

  getchar();
  printf("sorry?\n");
  mpz_clears(n, n_1_2, g, p, q, n2, NULL);
  return 0;
}

/*
g = 4935307733735729994278290975792000228775286930114042366725719878267551012927493448259270817917227756849322072959458794406806580920723349325531114469
a = 854851
b = 1011400
p = 8437905502983445042677582637893534375137565614989838462475696727313788501904161403475771835934720130340799646782932619714906025013322551788559197469878239
q = 9983140483800634632426126985832058062766650402234684899412786169759602188949733747138853010482968306554808689182393249326088351886439191015684338347893201
*/

from gmpy2 import invert, lcm
import libnum

n = 84236796025318186855187782611491334781897277899439717384242559751095347166978304126358295609924321812851255222430530001043539925782811895605398187299748256080526691975084042025794113521587064616352833904856626744098904922117855866813505228134381046907659080078950018430266048447119221001098505107823645953039
e = 58337
c = 13646200911032594651110040891135783560995665642049282201695300382255436792102048169200570930229947213493204600006876822744757042959653203573780257603577712302687497959686258542388622714078571068849217323703865310256200818493894194213812410547780002879351619924848073893321472704218227047519748394961963394668

p = 8437905502983445042677582637893534375137565614989838462475696727313788501904161403475771835934720130340799646782932619714906025013322551788559197469878239
q = 9983140483800634632426126985832058062766650402234684899412786169759602188949733747138853010482968306554808689182393249326088351886439191015684338347893201
assert p*q == n

phi = lcm(p-1, q-1)
d = invert(e, phi)
m = int(pow(c, d, n))
print(libnum.n2s(m))
# SangFor{0a8c2220-4c1b-32c8-e8c1-adf92ec7678b}

（表示最大收获就是学会C语言写多线程了。。。）