AIS3 pre-exam 2021 – Republic of South Africa

---

給了一個加密程式與 output
產生 key 的函式如下

def collision(m1, v1, m2, v2):
    return v1*(m1-m2)/(m1+m2) + v2*(2*m2)/(m1+m2), v1*(2*m1)/(m1+m2) + v2*(m2-m1)/(m1+m2)

def keygen(digits):     # Warning: slow implementation
    m1 = 1
    m2 = 10 ** (2*digits-2)
    v1 = gmpy2.mpfr(0)
    v2 = gmpy2.mpfr(-1)

    count = 0       # p+q
    while abs(v1) > v2 or v1 < 0:
        if v1 < 0:
            v1 = -v1
        else:
            v1, v2 = collision(m1, v1, m2, v2)
        count += 1

    while True:
        p = random.randint(count//3, count//2)
        q = count - p
        if isPrime(p) and isPrime(q):
            break
    return p, qCode language: PHP (php)

其中的 collision 就是物理上的彈性碰撞公式

跑下去後發現程式會跑不完
所以先把 digits 改小一點看看

恩…count = 993
m2 多加一個 0 試試看

！！！
3141 !?
看到長的像圓周率的東西與碰撞就讓我想起之前在 3B1B 的頻道上看到的 影片

其中碰撞次數會等於 pi 往後數共 兩者質量比的 100 的次方 這麼多位
如 1kg 與 10000000000 (100 ^ 5) 的物體相撞，會產生 314152 次的碰撞
因此可以推出 153 digits 要取 pi 的小數點後 152位

接下來就是產生 p , q 的過程

但因為這裡使用的是 randint ，所以沒辦法直接確定使用的是哪組 pq
回去看題目有給 n / e / c 
其中 n = pq
而如果 count 是 const 的話
n  = p * (count-p)
又一個固定邊長的矩形中，面積最大的必是正方形
所以 n 最大必是 p = q = count // 2
並當 p 越小，n 的值也會往下遞減
所以能找出一個 range => p = 1 ~ count// 2
其中 p * (count – p) 會是遞增，最大到 n^2
所以能透過二分搜尋法去減少搜尋的範圍

能拿到 p

"125271761150262906416707263718886403684050582091051005263078715902829301737825885945876611987225959401224076260783558207667345619556059984778330517466451"Code language: JSON / JSON with Comments (json)

拿到 p 後就能推出 RSA 的其他東西
並解出 plaintext來

p = 125271761150262906416707263718886403684050582091051005263078715902829301737825885945876611987225959401224076260783558207667345619556059984778330517466451
n = 23662270311503602529211462628663973377651035055221337186547659666520360329842954292759496973737109678655075242892199643594552737098393308599593056828393773327639809644570618472781338585802514939812387999523164606025662379300143159103239039862833152034195535186138249963826772564309026532268561022599227047
q = n // p
r = (p-1)*(q-1)
e = 65537
d = gmpy2.invert(e,r)

c = 11458615427536252698065643586706850515055080432343893818398610010478579108516179388166781637371605857508073447120074461777733767824330662610330121174203247272860627922171793234818603728793293847713278049996058754527159158251083995933600335482394024095666411743953262490304176144151437205651312338816540536
flg = int(pow(c,d,n))
flg_hex = hex(flg)[2:]
while flg_hex:
    print(chr(int(flg_hex[:2],16)),end="")
    flg_hex = flg_hex[2:]

Code language: PHP (php)

結果 flag 就是那個影片的網址XD