Clifford Cocks 的“非秘密加密”如何工作？

我已經閱讀了 Clifford Cocks “ A Note on ‘Non-secret Encryption’ ”，並認為我會嘗試實現這一點，但我似乎無法讓它發揮作用。我顯然錯過了一些東西。

從論文中：

1. 接收者選擇 2 個素數 $ P $ , $ Q $ 滿足條件：

一世。 $ P $ 不分 $ Q-1 $ .

ii. $ Q $ 不分 $ P-1 $ .

然後他傳送 $ N = PQ $ 給發件人。 2. 發件人有一條消息，由數字組成 $ C_1, C_2,\dots, C_r $ 和 $ 0 < C_i < N $ 他發送每個，編碼為： $ D_i $ 在哪裡 $ D_i = C_i^N \mod N $ . 3. 為了解碼，接收器通過歐幾里得算法找到數字 $ P\prime $ , $ Q\prime $ 滿足：

一世。 $ P\cdot P\prime = 1 \pmod{Q - 1} $

ii. $ Q\cdot Q\prime = 1 \pmod{P - 1} $

然後 $ C_i=D_i^{P\prime} \pmod Q $ 和 $ C_i = D_i^{Q\prime}\pmod P $ 所以 $ C_i $ 可以計算。

在我的程序中，我似乎無法恢復到原始消息。我不知道如何恢復 $ C_i $ 使用這種方法？我是否需要將這兩個計算結合起來 $ C_i $ 在第 3 步？

有什麼想法我哪裡出錯了嗎？

最後兩個方程不直接給你的值 $ C_i $ ，他們告訴你 Ci 的餘數除以 $ P $ 和 $ Q $ . 然後，您可以使用帶有此資訊的中國剩餘定理來產生 $ C_i $ （模組 $ N $ ) 你正在尋找的。

見en.wikipedia.org/wiki/Chinese_remainder_theorem（有一個算法可以解決兩個方程的情況）

NRCocker，我很想測試，即使不使用 CRT（對於 $ C < N^{1/2} $ ）。我對ruby​​ 進行了測試：

require 'openssl'
def extended_gcd(a, b)
 return [0, 1] if a % b == 0
 x, y = extended_gcd(b, a % b)
 [y, x - y * (a / b)]
end
def euclid(a, b)
 x, = extended_gcd(a, b)
 x += b if x < 0
 x
end
begin
 prnd = OpenSSL::BN::generate_prime(64, false).to_i
 qrnd = OpenSSL::BN::generate_prime(64, false).to_i
end while prnd.gcd(qrnd - 1) != 1 || qrnd.gcd(prnd - 1) != 1
P = prnd
Q = qrnd
p [:primes, P, Q]
N = P * Q
C = 1234567890 # this is plaintext
D = C.to_bn.mod_exp(N, N).to_i # is (C ^ N) mod N
p [:encoded, D]
PP = euclid(P, Q - 1) # find P^-1
QQ = euclid(Q, P - 1) # find Q^-1
CP = D.to_bn.mod_exp(PP, Q).to_i # is (D ^ (P^-1)) mod Q
CQ = D.to_bn.mod_exp(QQ, P).to_i # is (D ^ (Q^-1)) mod P
p [:decoded, CP, CQ]

範例輸出：

$ ruby cocks.rb
[:primes, 14416767379855795607, 14495845391589715337]
[:encoded, 190651495450681932039737793633345520369]
[:decoded, 1234567890, 1234567890]

附言。解碼任何 $ C < N $ ，您需要使用 CRT 結合 CP 和 CQ，我的範例：

IP = euclid(P, Q) # is (P^-1) mod Q
p [:crt, CQ + P * ((IP * (CP - CQ)) % Q)]

或者只是按照建議使用 RSA 解密：

IN = euclid(N, (P - 1) * (Q - 1)) # is (N^-1) mod phi(N)
p [:rsa, D.to_bn.mod_exp(IN, N).to_i]

引用自：https://crypto.stackexchange.com/questions/12687