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

Question

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?

Answer 1

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)

Answer 2

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]

Answer 3

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.