本来我是很菜的,没做出来几道题,在比赛后使用其他队伍的wp来学习一波。

My Simple Cipher

加密源码关键在

message = flag + "|" + key

encrypted = chr(random.randint(0, 128))

for i in range(0, len(message)):
  encrypted += chr((ord(message[i]) + ord(key[i % len(key)]) + ord(encrypted[i])) % 128)

由于key值非常小,所以在加密时循环使用密钥,这样使得整个解密过程变得简单。 首先,从最后开始将字符加上前一个字符再膜128,删除链接加密, 然后,通过"|"字符来还原密钥,由于密钥为13位,而且倒数第14位为"|", 可以还原第10个字符密钥,之后经过循环得到所有密钥。 最后,通过密钥直接得到所有明文。 (ps:当时做题的时候是手算的key以及其密文,这里放一个脚本)

#!/usr/bin/python2

import sys
import random

s = '7c153a474b6a2d3f7d3f7328703e6c2d243a083e2e773c45547748667c1511333f4f745e'.decode('hex')

# part 1: remove chaining encryption
dec1 = [ord(c) for c in s]
for i in range(len(s) - 1, 1, -1):
    dec1[i] = (dec1[i] - dec1[i-1]) % 128
dec1 = dec1[1:]
print dec1
# part 2: recover key since we know that 23rd character is '|'
key = [0] * 13
c = len(dec1) - 13 - 1
key[c % 13] = (dec1[c] - ord('|')) % 128

for _ in range(12):
    c = (c % 13) + len(dec1) - 13
    key[c % 13] = (dec1[c] - key[(c - (len(dec1) - 13))]) % 128

print key
message = ''
for i in range(0, len(dec1)):
    message += chr((dec1[i] - key[i % len(key)]) % 128)

print message

babyrsa

p = rand(2**1024)
q = 19 * p + rand(2**512)

p = next_prime(p)
q = next_prime(q)#获取q,p

e = 65537
d = mod_inverse(e, (p - 1) * (q - 1))

n = (p.to_i * q.to_i)#str.to_i转换为int

flag = File.binread('flag').unpack1("H*").to_i(16) * 256
while flag * 256 + 255 < n
  flag = flag * 256 + rand(256)
end

enc = mod_pow(flag, e, n)
dec = mod_pow(enc, d, n)
fail unless dec == flag
File.write('pubkey', [n, e].to_json)
File.write('flag.enc', enc)
File.write('privkey', [n, d].to_json)

关键源码如上,思路便是获取一个p然后通过p计算q来进行rsa。 但是根据q = 19 * p + rand(2**512)可以设$p_{rsa} = p + x$,$q_{rsa}=19p+y$ 由于rand跟next_prime太小,导致对高位没有影响,所以n可以近似等于$19pp$ 这样就可以求出p的高位值,之后,我们知道$N=(p+delta1)(19*p+delta2),而且,delta1只取决于next_prime,通过上一步,我们可以得到p的高位,我们可以做一个单变量多项式,进而求出n。 下面是sage代码:

hidden = 512
N = 386931010476066075837968435835568572278162262133897268076172926477773222237770106161904290022544637634198443777989318861346776496147456733417801969323559935547762053140311065149570645042679207282163944764258457818336874606186063312212223286995796662956880884390624903779609227558663952294861600483773641805524656787990883017538007871813015279849974842810524387541576499325580716200722985825884806159228713614036698970897017484020439048399276917685918470357385648137307211493845078192550112457897553375871556074252744253633037568961352527728436056302534978263323170336240030950585991108197098692769976160890567250487423
n = 386931010476066075837968435835568572278162262133897268076172926477773222237770106161904290022544637634198443777989318861346776496147456733417801969323559935547762053140311065149570645042679207282163944764258457818336874606186063312212223286995796662956880884390624903779609227558663952294861600483773641805524656787990883017538007871813015279849974842810524387541576499325580716200722985825884806159228713614036698970897017484020439048399276917685918470357385648137307211493845078192550112457897553375871556074252744253633037568961352527728436056302534978263323170336240030950585991108197098692769976160890567250487423
e = 65537
ct = 238128932536965734026453335534508678486770867304645614119195536048961186128744314667991999168452564298994773996973787655358503271491181214369796509942047091225518293577154563021214085132019889288510474458242494876257330038265066123460887568813277411779817556316602871932730284368524299559699693787556478631297630514938453794107136748994144175123917418701679413905695916367530746728699301383100433069740863537869450361306987480687067608102552418211244703552910903168179094472596152349098076535870469807035136435631458879919434041758274344589567529971195683495146426258135341109919085270442486183365562919531353370683625

p_approx = isqrt(N/19)
q_approx = 19*p_approx + 2**512

F.<x> = PolynomialRing(Zmod(N), implementation='NTL')
f = x - q_approx
d = f.small_roots(X=2**hidden, beta=0.5)
if d:
    d = d[0]
    print('delta',d)
    print('q = q_approx - delta', q_approx - d)
    q = q_approx - d
    p = int(N)/int(q)
    phi = (p-1)*(q-1)
    d = inverse_mod(int(e), int(phi))
    print(hex(long(pow(ct,d,n)))[2:-1].decode("hex"))

原wp:p4-team

babydlp

这是道部署在服务端的,源码如下:

# Python 3
from signal import alarm
from Crypto.Util.number import *

p = 160634950613302858781995506902938412625377360249559915379491492274326359260806831823821711441204122060415286351711411013883400510041411782176467940678464161205204391247137689678794367049197824119717278923753940984084059450704378828123780678883777306239500480793044460796256306557893061457956479624163771194201
g = 2

bits = size(p)

with open("flag", "r") as f:
    flag = f.readline().strip().encode("latin1")
    m = bytes_to_long(flag)

def run(fin, fout):
    alarm(1200)
    try:
        while True:
            line = fin.readline()[:4+bits//4]
            s = int(line, 16) # Note: input is HEX
            c = pow(g, m ^ s, p)
            fout.write(hex(c) + "\n")
            fout.flush()
    except:
        pass

if __name__ == "__main__":
    run(sys.stdin, sys.stdout)

关键就是c = pow(g, m ^ s, p), 我们可以知道关于密文跟输入的关系,

1.Send 0 as input to recover original c value from the server

2.Send 1,2,4,...,2**k as input and check if result == c * pow(2, 2**k, p) % p and if it is then k-th bit was originally 0, otherwise it was 1

这样可以得到整个密文的二进制数值。

#!/usr/bin/env python3
from socket import socket

p = 160634950613302858781995506902938412625377360249559915379491492274326359260806831823821711441204122060415286351711411013883400510041411782176467940678464161205204391247137689678794367049197824119717278923753940984084059450704378828123780678883777306239500480793044460796256306557893061457956479624163771194201
E = 10e-8

def calc(mul, x1, x2):
  return abs((x1 - (mul * x2)%p) % p) < E , abs((x2 - (mul * x1)%p) % p) < E

res = ''
for i in range(260*16):
  mul = 2 if i == 0 else (mul**2 % p)
  a,b = map(lambda x: hex(int(x, 2))[2:].encode()+b'\r\n',('1'+res, '0'+res))

  with socket() as s:
    s.connect(('ppc2.chal.ctf.westerns.tokyo', 28459))
    s.send(a)
    a = s.recv(2048).strip()[2:].decode()
    s.send(b)
    b = s.recv(2048).strip()[2:].decode()

  a,b = map(lambda x:int(x, 16), (a,b))
  v1, v2 = calc(mul, a, b)
  if v1 and v2:
    print('WRONG!')
    print(res, v1, v2)
    exit()
  res = ('1' if not v1 else '0') + res
  print('res:', res)

更新于2017.9.9,翻译至ctf-time write-up,还有两道题改天再研究吧