Midnight Sun CTF2022

Pelle’s Rotor-Supported Arithmetic

解析：

• 求n

  取c = -1，rot = 0。有如下公式（根据e * d = 1+k * φ(n)可知d为奇数）
  $$
  r = -1^d\ mod\ n
  $$
  因为d为奇数
  $$
  r = -1\ mod\ n
  $$
  又有
  $$
  n-1 = -1\ mod\ n
  $$
  所以
  $$
  n = r+1
  $$

• 求d

  注意到oracle()主要是对d进行循环移位，故可以依次求出d的每一位。

  举个例子（借鉴来的）：

  • 假设d = 314159，向服务器询问两次，为(2,0)和(2,1)。
  • 得到$r = 2^{314159}$和$s = 2^{141593}$。
  • 然后为了构建等式，把上述式子转换成$2^{3141593}$，于是有$r^{10}*2^3 = s*2^{3*10^{6}}$。
  • 显然，我们要求的是3，设其为x，6为d的长度，也是未知的，设其为len。故有一般式$r^{10}*2^x = s*2^{x*10^{len}}$。
  • 根据测试发现len为307左右，可以进行枚举。

• 分解n

  利用Wienner Attack脚本。

(没有环境复现，如有错误的地方请指出)

from pwn import *
import gmpy2
from Crypto.Util.number import *

e = 65537
sh = remote('pelle-01.hfsc.tf',4591)
sh.recvuntil(b'flag ')
Cipher = sh.recv()[:-1].decode()
print(f'Cipher = {Cipher}')
print(sh.recv())
c_list = []

def get(c,i):
    sh.sendline(b'1')
    sh.recv()
    sh.sendline(str(c).encode())
    sh.recv()
    sh.sendline(str(i).encode())
    return sh.recv()[:-1].decode()

def get_di(len,r,s):
    if isinstance(len, int)://方便复用
        len = [len]
    for dlen in len:
        for x in range(10):
            tmp1 = pow(r,10,n)*2**x%n
            tmp2 = s*pow(2,x*10**dlen,n)%n
            if (tmp1-tmp2)%n == 0:
                return dlen,x

n = get(-1,0)+1
print(f'n = {n}')

ps = [get(2,i) for i in range(315)]
len, d0 = get_di([306,307,308,309],ps[0],ps[1])
di_list = [get_di(len,ps[i],ps[i+1])[1] for i in range(1,314)]
d = int(''.join(i for i in [d0]+di_list)[:len])
print(f'd = {d}')

（嫖个脚本）

from gmpy2 import iroot,invert

n = 43047796890477362990074961769201922093931501549521114743916627406636416622979445051218421149675256799232393301700370094540087679119082880899747691935251456178408503271262210863920917237676311115019888447360967178340255706657371448083420218420057544839628399548904356647638728064251771091862957676254700954117
e = 27674287480195801722658014392785989313845949971533997686660899124104025285859437857972359428690936714607919108095274315625722478853856599143509311634893475488768721169431521077251366133165140420429800291880801747490176817398575093644983093206936398362605552523502972162034264567777255223024221794336695299713
 

def wienerAttack(_e, _n):
    con_frac = continued_fraction(_e / _n)
    conv = con_frac.convergents()
    for _ in conv:
        k, dg = _.numerator(), _.denominator()
        if k == 0 or dg == 0:
            continue
        _phi = _e * dg // k
        if (_n - _phi + 1) % 2 == 0 and iroot(abs(pow((_n - _phi + 1) // 2, 2) - _n), 2)[1]:
            delta = (_phi - _n - 1) ** 2 - 4 * _n
            _p = (_n + 1 - _phi - int(iroot(delta, 2)[0])) // 2
            _q = _n // _p
            assert _n % _q == 0
            return _p, _q

p, q = wienerAttack(e, n)
print(p)
print(q)

---

参考：

Neobeo/Midnight-Sun (github.com)