# How does Clifford Cocks 'Non-Secret Encryption' work?

I have read Clifford Cocks "A Note on 'Non-secret Encryption'" and thought I would try to implement this, but I don't seem to be able to get it to work. I'm obviously missing something.

From the paper:

1. The receiver picks 2 primes $P$, $Q$ satisfying the conditions:

i. $P$ does not divide $Q-1$.

ii. $Q$ does not divide $P-1$.

He then transmits $N = PQ$ to the sender.

2. The sender has a message, consisting of numbers $C_1, C_2,\dots, C_r$ with $0 < C_i < N$ He sends each, encoded as: $D_i$ where $D_i = C_i^N \mod N$.

3. To decode, the receiver finds, by Euclid's Algorithm, numbers $P\prime$, $Q\prime$ satisfying:

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

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

Then $C_i=D_i^{P\prime} \pmod Q$ and $C_i = D_i^{Q\prime}\pmod P$ and so $C_i$ can be calculated.

In my program I don't seem to be able to reverse back to the original message. I don't see how I can recover $C_i$ using this method? Do I need to combine the two calculations of $C_i$ in step 3?

Any ideas where I am going wrong?

• In addition to Thomas's correct comment, there is an alternative way to look at this; Cocks message is precisely RSA with $N=e$; that is, the same value is used for the modulus and the public exponent. What Mr. Cocks specifies for decryption is the standard method for doing RSA decryption using the Chinese Remainder Theorem; details on precisely how to do that is spelled out in, for example, PKCS #1. – poncho Jan 3 '14 at 4:53
• @Thomas do you mind to add your comment as an answer? – DrLecter Jan 5 '14 at 20:22
• The link does not work. Another variants: 1 (looks like original report) and 2: from google scholar. – Alexey Ustinov Feb 27 '18 at 13:09

The two last equations don't directly give you the value of $C_i$, they are telling you the values of the remainder of Ci when divided by $P$ and $Q$. You then use the Chinese Remainder Theorem with this information to produce the value of $C_i$ (modulo $N$) that you are looking for.

See en.wikipedia.org/wiki/Chinese_remainder_theorem (there is an algorithm for solving it for the case of two equations)

NRCocker, I was curious to test, and it was worked for me even without using CRT (for $C < N^{1/2}$). There is my test on 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]


Example output:

$ruby cocks.rb [:primes, 14416767379855795607, 14495845391589715337] [:encoded, 190651495450681932039737793633345520369] [:decoded, 1234567890, 1234567890]  ps. To decode for any$C < N$, you'll need to combine CP and CQ using CRT, my example: IP = euclid(P, Q) # is (P^-1) mod Q p [:crt, CQ + P * ((IP * (CP - CQ)) % Q)]  Or just use RSA decrypt as suggested: IN = euclid(N, (P - 1) * (Q - 1)) # is (N^-1) mod phi(N) p [:rsa, D.to_bn.mod_exp(IN, N).to_i]  • Specifically, the condition for "not needing the CRT" is when$C < \min(P, Q)$, in which case$C \bmod P = C \bmod Q = C\$. – Ilmari Karonen Apr 29 '20 at 8:56

The following two videos are recommended. They show how to apply Chinese Remainder Theorem (CRT) and implement Cocks' public encryption system.

I recommend the following two videos:

• "Demo of Chinese Remainder Theorem" by "D G" (24min) which explains how $$(x\bmod p,x\bmod q)$$ can be used to find $$(x\bmod n)$$

• "Cocks' Non-secret Encryption (GCHQ) vs RSA" also by "D G" (23min) which shows how in Cock's method the data is decrypted in two steps. The first step decrypts the incoming ciphertext $$d$$ as $$d^{p_1}\bmod q$$ and the second one does the same for $$q$$: $$d^{q_1}\bmod p$$ such that $$p\cdot p_1=1\pmod {q-1}$$ and $$q\cdot q_1=1\pmod {p-1}$$.

The reason decryption works is the following: $$d^{p_1} = c^{p\cdot q \cdot p_1} = c^q \pmod q = c \bmod q$$ due to Fermat's little theorem. Similarly, $$d^{q_1} = c^{p\cdot q\cdot q_1} = c^p \pmod p = c \bmod p.$$ We have two pairs $$(c \bmod p, c \bmod q)$$. We will have to use the Chinese Remainder Theorem to find $$c \bmod n$$. In Cocks paper, they used $$c$$ for plaintext data.

• I edited your comments into the answer, though I'm not sure I got 100% of their meaning right, would you mind and edit your answer to clarify it wherever I messed up? – SEJPM Apr 27 '20 at 21:01
• Very nice. Thanks for summarizing the video. The encryption exponent is n (in RSA it is e). There are two decryption exponents (p_1, q_1). – user3150318 Apr 29 '20 at 0:26