Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
2  
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 at 4:53
    
@Thomas do you mind to add your comment as an answer? –  DrLecter Jan 5 at 20:22

2 Answers 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]
share|improve this answer

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)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.