KTH Exchange 45: 理想與現實

cryptography assignment, deadline 剛好在 KTH challenge 以及我出題的 Codeforces round 附近, 很多題目都沒有時間仔細想
與 lecture 不同, assignment 有不少是 practical 的題目
有些是要寫 program 交上 Kattis judge

今次的題目有求 a^e mod n, chinese remainder, 看下去很熟悉
不過 input size 是由 256 bit 起跳, multiple test case, 而且 time limit 只有 1 秒 !
要寫 bignum division 和 mod, 還要 optimize, 花了不少時間
最後一條是 given (N, e, d), factorize N
搞完一大輪後還是 TLE, 忍不住轉去用 Java BigInteger

然後功課還有「閱讀理解」題
如果有兩個 RSA modulus share prime factor, 只要求它們 gcd 可以輕鬆破解
雖然理論上 RSA 用的 modulus 應該是由 random 的 prime 相乘
但是現實中因為用的 randomness 有問題, 而會導致使用 same prime
這個倒是挺有趣的, 完全沒有想過這個問題
所以我決定稱這份功課為「理想與現實」