考完試才知道答案,我真是一個人才

先來一條蠢問題

r = random number

C = M + rK

你知道K的話如何由C找M?

答案超簡單: C mod K = M
可恨的是當時想不到....



題目是 C1 = M + r1 K1 , C2 = M r2 K2 (K1 ,K2 固定, r1 r2每次隨機, M一樣)
(C1 , C2) 為一組 ciphertext
考完試才想問 C2有屁用... C2比較像MAC

分問題
知道幾組M和C的話K就會被知道
有n組,每個叫 (M1,C1) , (M2,C2)... (Mn , Cn)

GCD (C1 - M1, C2 - M2, ... Cn -Mn) 就找到 K了
因為 Cn - Mn = rn K, K就是 GCD

n 是 2的話 ... GCD(r1,r2)是1的話也能找到 K
n 越大的話 GCD(r1,r2 ... rn)是1的機會就越大, K 99.9...%會被算出來

一開始的部分(如何用K把C變M)想不到,之後的也做不了

題目稍稍記錯
M = M mod K1 K2
直接 M mod K1 和 M mod K2 還欠一些才找到 M mod K1 K2
改一改名字 (m1 , m2)

C1 = M + r1 K1
C2 = M + r2 K2

m1 = M mod K1 (M mod K1 = C1 mod K1)
m2 = M mod K2 (M mod K2 = C2 mod K2)

這裡用 Chinese Remainder Theorem 就能找回 M (K1, K2 co-prime)

分題1
給你 (C11,C12) , (C21,C22)
請偽造Decrypt 結果和 M1 + M2 , M1 M2 一樣的 (C31,C32)出來

知道了 decrypt方法就能簡單偽造 囧 (假設加完和乘完也不會大過 K1K2, 大過的話會被 K1K2 mod掉而看不到原有數字)

C31 = C11 + C21 mod K1
C32 = C12 + C22 mod K2

之後的解密方法也是一樣
因為解密時都是用同餘數加乘

例子:
x = 3 mod 4
x = 3 mod 7

(C11, C12) = (203, 213)
M = 3
=========================

x = 1 mod 4
x = 5 mod 7

(C21, C22) = (441, 89)
M = 5
=========================

(C11 + C21) mod 4 = (3 + 1) mod 4
(C12 + C22) mod 7 = (3 + 5) mod 7

m1 = 0 mod 4
m2 = 1 mod 7
M = 8 mod 28 (就是3 + 5)

分題2
稍稍忘了...
知道2組 (C1 , C2) 和它們的M 就能知道 K1, K2
忘記了 GCD (r1, r2)是否1 ... 不是1的話只憑2組不一定找到正確的K

例子
(C1, C2) = (203, 213)
M = 3
========================
(C1, C2) = (441, 89)
M = 5

還是用 GCD(C - M)就可以

另一條

http://homes.cerias.purdue.edu/~crisn/courses/cs555_Fall_2005/cs555_lect16.pdf 的 slide 17
該死的av(-rv -1) ....