Maojui

AIS3 2020 EOF - RSACTR Revenge (Crypto, 500)

2020-01-18

Challenge

題目:server.py

Solution

這次只剩下兩個選項,給你做四個動作的機會,很明顯,除了 info 以外還要三次 get flag 才能解開

  1. info
  2. get flag

選擇 1 他一樣會給你公鑰 (N, e)

而每 get flag 一次,都會回你:

FLAG1 : pow( nonce + 2020, d, n) + flag1

FLAG2 : pow( nonce + 4040, d, n) + flag2

但是這裡不一樣的地方是,你可以 get 三次 flag ,得到:

FLAG1 : pow( nonce + 2020, d, n) + flag1

FLAG2 : pow( nonce + 4040, d, n) + flag2

FLAG3 : pow( nonce + 6060, d, n) + flag1

FLAG4 : pow( nonce + 8080, d, n) + flag2

FLAG5 : pow( nonce + 10100, d, n) + flag1

FLAG6 : pow( nonce + 12120, d, n) + flag2

但始終無法知道 nonce 是多少。

手邊擁有的情報只有 e = 4097,和兩組 Flag,先針對一組:

FLAG1 : pow( nonce + 2020, d, n) + flag1

FLAG3 : pow( nonce + 6060, d, n) + flag1

FLAG5 : pow( nonce + 10100, d, n) + flag1

對這三個,直接做 4097 次方可以得到:

$$(nonce+2020)^{ed} + …. + flag1^{4097}$$

$$(nonce+6060)^{ed} + …. + flag1^{4097}$$

$$(nonce+10100)^{ed} + …. + flag1^{4097}$$

相減後會得到兩個含有 flag1 因式的方程式,把這兩個方程式做 GCD

FLAG{GCdISSuchaGO0DalgOriTHM}

Script : solve.sage