Problems & Puzzles: Problems

Numerical examples of the solutions to the Problem 34, sent by Chris Nash & Eric Brier

I proposed to both Eric & Chris, to work their respective examples starting from a precise statement of the problem. This is the statement proposed:

Sam and Joe know one and the same composite number N. Both know that N has two primes factors, p & q. Only Sam knows p & q. How can Sam prove to Joe that he (Sam) knows p & q without ever revealing p & q?

I proposed also the following values of p & q:

p = 63*2^280+1
q = 197*2^300-3

O.K. here are their respective numerical calculations:

A. Chris Nash example, based on the RSA cryptosystem approach:

"Here is an example of the RSA scheme in operation. I will use your description and your sample values. Sam and Joe both know N, but only Sam knows the factorization N=p*q.

Sam first calculates (p-1)(q-1) and selects a random number r with no factor in common with (p-1)(q-1). Here is the number that Sam chose (base 16). (For convenience I made this number half the size of N).

Sam calculates s, such that rs=1 mod (p-1)(q-1). This can be done as part of the gcd calculation.

s=1bd0f3795988f526a9b9d12cc5c885c1a4487c905cb64c9b5a6fec8d2c2e8b78340ff1e/
cb51cf81fb63a870138679886d5fcbe29761c19e937c40f88bfef5205ecf769498d101e/
7c7aae5

Sam now picks his secret message: This message proves I have factored N and converts it to a number, using ASCII (note this number has less bits than N).

m=54686973206d6573736167652070726f7665732049206861766520666163746f7265642/
04e

Now Sam encrypts the message using his secret key, x=m^s mod n

41bd96abfdc19cc90a654551b9153c3ce0b6508df7a42475fc91be50de2a68c7e7c1b88/
80dba0

Now Joe receives the message, he knows x, r, and n. Now he calculates x ^r mod n, retrieves the original message m, and when converted to ASCII he retrieves the original message.

I also include the source code used to generate this results, for programmers in C using the GNU multiprecision library GMP. (Note the calculation x^r mod n is one line in most mathematics libraries). Hope this helps!. Chris"

*********

#include <stdio.h>
#include <gmp.h>
char *sMessage="This message proves I have factored N";
char sHexBuffer[200];
char sOutput[200];
int main(int argc,char *argv[])

{
mpz_t p;
mpz_t q;
mpz_t n;
mpz_t r;
mpz_t s;
mpz_t m;
mpz_t g;
mpz_t x;
char *sText=sMessage;
char *sWrite=sHexBuffer;
mpz_init(p);
mpz_init(q);
mpz_init(n);
mpz_init(r);
mpz_init(s);
mpz_init(m);
mpz_init(g);
mpz_init(x);

// calculate p,q and n
mpz_set_ui(p,63);
mpz_mul_2exp(p,p,280);
mpz_set_ui(q,197);
mpz_mul_2exp(q,q,300);
mpz_sub_ui(q,q,3);
mpz_mul(n,p,q);

// choose a random value of r, make it about sqrt(n)
mpz_random(r,mpz_size(n)/2);

// calculate m=(p-1)(q-1)
mpz_sub_ui(p,p,1);
mpz_sub_ui(q,q,1);
mpz_mul(m,p,q);

// keep adding 1 to r until gcd is 1
while(1)
{
mpz_gcdext(g,s,NULL,r,m);
if(0==mpz_cmp_ui(g,1)) break;
}

// note that gcdext solves sr+m?=g, so s is indeed a multiplicative
inverse mod m

// just make sure it is in the range 0 to m-1
mpz_mod(s,s,m);

// write this out as a hex number
mpz_get_str(sHexBuffer,16,r);
printf("r=%s\n",sHexBuffer);

// write this out as a hex number
mpz_get_str(sHexBuffer,16,s);
printf("s=%s\n",sHexBuffer);

// convert the message to its hex form then to the number x
while(*sText)
{
int i=0x00f0&(*sText);
i>>=4;
*sWrite++="0123456789ABCDEF"[i];
i=0x000f&(*sText);
*sWrite++="0123456789ABCDEF"[i];
sText++;
}
*sWrite=0;
printf("m=%s\n",sHexBuffer);

// calculate x
mpz_set_str(x,sHexBuffer,16);

// encode the message as x^s mod N
mpz_powm(x,x,s,n);

// write this out as a hex number
mpz_get_str(sHexBuffer,16,x);
printf("x=%s\n",sHexBuffer);

// Here is what the decoder does. Note it uses only x, r, and n
// decode the message as x^r mod N
mpz_powm(x,x,r,n);

// write this out as a hex number
mpz_get_str(sHexBuffer,16,x);
printf("m=%s\n",sHexBuffer);

// write the ASCII form, this method is a little easier
sWrite=sOutput+200;
*--sWrite=0;
while(mpz_cmp_ui(x,0))
{
unsigned long xx=mpz_mod_ui(r,x,256UL);
if((xx<32)||(xx>126)) xx='?';
*--sWrite=(char)xx;
mpz_fdiv_q_2exp(x,x,8);
}

printf("Decoded message=%s\n",sWrite);
mpz_clear(x);
mpz_clear(g);
mpz_clear(m);
mpz_clear(s);
mpz_clear(r);
mpz_clear(n);
mpz_clear(q);
mpz_clear(p);
return 0;

B. Eric Brier example, from an idea original by him.

For those not skilled in the C language, I ( CR) have written a code in Ubasic (by Yuji Kida)to solve the same problem than Chris Nash (under the RSA cryptosystem approach, as suggested Jud McCranie)

10 input "The two primes P & Q>P are?";P,Q
20 N=P*Q:Z=(P-1)*(Q-1)
30 R=P+irnd:if GCD(R,Z)<>1 then goto 30:'R=public key for Joe who also knows N
40 S=modinv(R,Z):' S=secret key known only by Sam
50 input "a number M<N";M:'M=the message composed by Sam as signal of his knwoledge of p & q.
60 X=modpow(M,S,N):'X=the message M of and coded by Sam sent to Joe
70 MD=modpow(X,R,N):'MD=M =the message X decoded by Joe using his info. R & N.
80 if MD<>M then print "Error":end
90 print P,Q,N,Z,R,S,M,X,MD:end

This is the output of the above code for the input: P=63*2^280+1, Q=197*2^300-3 & M=1000000000352138900000000001:

(Note: M is just my phone number as a nut of a dummy number 1000...0001)

P=122388140210220931467926100129881691118471630860284789838864181813550969967928/
135385089

Q=40129608733789375899488380061664749772713927355218944137531966852281311605337/
7331118129283069

N=49113881802923205955598348613997460408416242779122242322774985426703159372754/
6720552131509528575723749826792904894192325591187289706347251310363954474438053/
87608573813533802758141

Z=49113881802923205955598348613997460408416242779122242322774985426703159372754/
6720552127496566478463410134634752208764849315098985786109048293762859400568104/
58004226514487538089984

R=12238814021022093146792610012988169111847163086028478983886418181355096996792/
8135414811

S=37805974923353551526720478684718535987976273220253018027811288808056792118079/
8842481772165346009931271737880899094993962407013946115283339547878457504380675/
20541339690374032541203

M=10000000000352138900000000001

X=22102394250777952241746601779634211462511945743017652530231370881530536541960/
0114408412195991001471020654285444932198739534548770537804633268746926813060464/
837278930246510038440

MD=10000000000352138900000000001

***

 Records   |  Conjectures  |  Problems  |  Puzzles