mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math > Number Theory Discussion Group

Reply
 
Thread Tools
Old 2019-03-28, 20:50   #1
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

3×1,049 Posts
Default RSA on Frobenius

Let n = p*q.

Choose e: gcd(e,(p^2 - 1)*(q^2 - 1)) == 1

Compute d: d = e^-1 (mod (p^2 - 1)*(q^2 - 1))

Then encode m = m1x + m2 to the cipher number c = m^e (mod n, x^2-a*x+1) for some a: 2<a<(n-2). (m1 non zero.)

To decipher compute c^d (mod n, x^2-a*x+1).

Because exponentiation over x^2-a*x+1 in ~2 log2 multiplications and modular reductions, there is little overhead in the encryption of m1 and m2 and the decryption of the code word.

The strength of the system relies on the factorisation of n. Note d<n^2

Contrast the above with this 2012 paper by Lhoussain El Fadil.

Last fiddled with by paulunderwood on 2019-03-28 at 21:01
paulunderwood is offline   Reply With Quote
Old 2019-03-29, 13:19   #2
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

2×29×53 Posts
Default

The modulus (p^2 - 1)*(q^2 - 1) is certainly sufficient, but may be a bit larger than necessary.

The multiplicative order depends on the quadratic character of a^2 - 4 (mod p) and (mod q). If kronecker(a^2 - 4,p) = -1 the order (mod p) will divide p+1; if +1 it will divide p-1. Similarly for q.

There are several possible cases.

I suppose gcd(a^2 - 4, n) should be checked for the sake of thoroughness
:-D
Dr Sardonicus is offline   Reply With Quote
Old 2019-03-29, 15:05   #3
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

23·349 Posts
Default

I know I have asked this before, but I forgot and cannot find the old question and answer:

c = m^e (mod n, x^2-a*x+1)

What is the definition of a number mod 2 different numbers?
ATH is offline   Reply With Quote
Old 2019-03-29, 16:27   #4
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

54416 Posts
Default

Quote:
Originally Posted by ATH View Post
I know I have asked this before, but I forgot and cannot find the old question and answer:

c = m^e (mod n, x^2-a*x+1)

What is the definition of a number mod 2 different numbers?
Both n and \(x^2-ax+1\) are regarded as equivalent to 0.
The polynomial is monic and, assuming it is also irreducible, this gives a number system
with \(n^2\) elements, namely \(rx+s\) where \(r,s\in\{0,1,\ldots,n-1\}\).
Nick is offline   Reply With Quote
Old 2019-04-03, 18:44   #5
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

314710 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
The modulus (p^2 - 1)*(q^2 - 1) is certainly sufficient, but may be a bit larger than necessary.

The multiplicative order depends on the quadratic character of a^2 - 4 (mod p) and (mod q). If kronecker(a^2 - 4,p) = -1 the order (mod p) will divide p+1; if +1 it will divide p-1. Similarly for q.

There are several possible cases.

I suppose gcd(a^2 - 4, n) should be checked for the sake of thoroughness
:-D
I tend to agree but that kronecker(a^2 - 4, n) == -1 should be checked -- though I cannot see a reason.
paulunderwood is offline   Reply With Quote
Old 2019-04-04, 10:44   #6
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

3×1,049 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
I tend to agree but that kronecker(a^2 - 4, n) == -1 should be checked -- though I cannot see a reason.
It seems to be that choosing 2 < a < n-2: kronecker(a^2 - 4, p) == -1 and kronecker(a^2 - 4, q) == -1 will give the strongest results i.e. the multiplicative order of invertible elements will divide lcm(p^2 - 1, q^2 - 1).

I suppose gcd(a^3 - a, n) would also be wise to check.

Last fiddled with by paulunderwood on 2019-04-04 at 10:57
paulunderwood is offline   Reply With Quote
Old 2019-04-15, 14:54   #7
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

C4B16 Posts
Default

I ran a couple of naive timing tests on RSA and RSA-Frobenius. Both use "safe primes" w.r.t (p-1)*(q-1). That is both (p-1)/2 and (q-1)/2 are prime. But should RSA-frobenius be using "extra safe primes" w.r.t. (p^2-1)*(q^2-1)?

RSA:
Code:
gettime();E=512;for(count=1,10,m=random(2^(2*E));
p=randomprime(2^E);while(!ispseudoprime((p-1)/2),p=randomprime(2^E));
q=randomprime(2^E);while(!ispseudoprime((q-1)/2),q=randomprime(2^E));
n=p*q;e=17;d=lift(Mod(e,(p-1)*(q-1))^-1);c=Mod(m,n)^e;dm=Mod(c,n)^d);
gettime()
35713
RSA-Frobenius:
Code:
gettime();E=512;for(count=1,10,m=random(2^(2*E))*x+random(2^(2*E));
p=randomprime(2^E);while(!ispseudoprime((p-1)/2),p=randomprime(2^E));
q=randomprime(2^E);while(!ispseudoprime((q-1)/2),q=randomprime(2^E));
n=p*q;a=3;while(gcd(a^3-a,n)!=1||
kronecker(a^2-4,p)!=-1||kronecker(a^2-4,q)!=-1,a++);
e=17;while(gcd(e,(p^2-1)*(q^2-1))!=1,e++);
d=lift(Mod(e,(p^2-1)*(q^2-1))^-1);
c=Mod(Mod(1,n)*m,x^2-a*x+1)^e;dm=Mod(Mod(1,n)*c,x^2-a*x+1)^d);gettime()
38840
Since the message space of RSA-Frobenius is twice that of RSA, it is considerably faster, nearly twice the speed (and the decryption key is much bigger!) I guess the results are skewed because of the taken to find safe primes...

So with one key generation and 10 messages or 20 in the case with RSA-Frobenius:

RSA:
Code:
gettime();E=512;
p=randomprime(2^E);while(!ispseudoprime((p-1)/2),p=randomprime(2^E));
q=randomprime(2^E);while(!ispseudoprime((q-1)/2),q=randomprime(2^E));n=p*q;e=17;d=lift(Mod(e,(p-1)*(q-1))^-1);
for(count=1,10,m=random(2^(2*E));c=Mod(m,n)^e;dm=Mod(c,n)^d);gettime()
15232
RSA-Frobenius:
Quote:
gettime();E=512;
p=randomprime(2^E);while(!ispseudoprime((p-1)/2),p=randomprime(2^E));
q=randomprime(2^E);while(!ispseudoprime((q-1)/2),q=randomprime(2^E));
n=p*q;a=3;while(gcd(a^3-a,n)!=1||
kronecker(a^2-4,p)!=-1||kronecker(a^2-4,q)!=-1,a++);
e=17;while(gcd(e,(p^2-1)*(q^2-1))!=1,e++);for(count=1,10,m=random(2^(2*E))*x+random(2^(2*E));
d=lift(Mod(e,(p^2-1)*(q^2-1))^-1);c=Mod(Mod(1,n)*m,x^2-a*x+1)^e;
dm=Mod(Mod(1,n)*c,x^2-a*x+1)^d);gettime()
3885
Nearly 8 times as fast! I did say "naive"

Another test with the same key generation:

Code:
ettime();E=512;
p=randomprime(2^E);while(!ispseudoprime((p-1)/2),p=randomprime(2^E));
q=randomprime(2^E);while(!ispseudoprime((q-1)/2),q=randomprime(2^E));n=p*q;a=3;
while(gcd(a^3-a,n)!=1||kronecker(a^2-4,p)!=-1||kronecker(a^2-4,q)!=-1,a++);e=17;
while(gcd(e,(p^2-1)*(q^2-1))!=1,e++);print(gettime());
for(count=1,100,m=random(2^(2*E))*x+random(2^(2*E));d=lift(Mod(e,(p^2-1)*(q^2-1))^-1);c=Mod(Mod(1,n)*m,x^2-a*x+1)^e;dm=Mod(Mod(1,n)*c,x^2-a*x+1)^d);print(gettime());
d=lift(Mod(e,(p-1)*(q-1))^-1);for(count=1,100,m=random(2^(2*E));c=Mod(m,n)^e;
dm=Mod(c,n)^d);gettime()
1573
684
64
Here RSA is quicker than RSA-Frobenius 128ms as opposed to 684ms. Even with some more efficient programming of working mod x^2-a*x+1, I think the original RSA wins for speed (but not decryption key length).

So final test: same key sizes and a 100 messages for RSA and 200 messages for RSA-Frobenius:

RSA:
Code:
gettime();E=1024;
p=randomprime(2^E);while(!ispseudoprime((p-1)/2),p=randomprime(2^E));
q=randomprime(2^E);while(!ispseudoprime((q-1)/2),q=randomprime(2^E));
n=p*q;e=17;d=lift(Mod(e,(p-1)*(q-1))^-1);
for(count=1,100,m=random(2^(2*E));c=Mod(m,n)^e;dm=Mod(c,n)^d);gettime()
69953
RSA-Frobenius:
Code:
gettime();E=512;
p=randomprime(2^E);while(!ispseudoprime((p-1)/2),p=randomprime(2^E));
q=randomprime(2^E);while(!ispseudoprime((q-1)/2),q=randomprime(2^E));
n=p*q;a=3;while(gcd(a^3-a,n)!=1||kronecker(a^2-4,p)!=-1||
kronecker(a^2-4,q)!=-1,a++);e=17;while(gcd(e,(p^2-1)*(q^2-1))!=1,e++);
for(count=1,100,m=random(2^(2*E))*x+random(2^(2*E));
d=lift(Mod(e,(p^2-1)*(q^2-1))^-1);c=Mod(Mod(1,n)*m,x^2-a*x+1)^e;dm=Mod(Mod(1,n)*c,x^2-a*x+1)^d);gettime()
2044
30 times as fast!

Last fiddled with by paulunderwood on 2019-04-15 at 15:52
paulunderwood is offline   Reply With Quote
Old 2019-04-15, 22:44   #8
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

3×1,049 Posts
Default

Key generation is very time-consuming. Here I compare 2048 bit messages with ~2048 bit decryption keys:

RSA-2048:
Code:
{gettime();E=1024;for(count=1,4
,p=randomprime(2^E);while(!ispseudoprime((p-1)/2),p=randomprime(2^E));
q=randomprime(2^E);while(!ispseudoprime((q-1)/2),q=randomprime(2^E));
n=p*q;e=17;d=lift(Mod(e,(p-1)*(q-1))^-1));
print("4 keys generated:"gettime());
for(count=1,1000,m=random(2^(2*E));
c=Mod(m,n)^e;dm=Mod(c,n)^d);print("1000 messages:"gettime())}
4 keys generated:384865
1000 messages:3541
RSA-Frobenius-1024
Quote:
{gettime();E=512;for(count=1,4,
p=randomprime(2^E);while(!ispseudoprime((p-1)/2),p=randomprime(2^E));q=randomprime(2^E);while(!ispseudoprime((q-1)/2),q=randomprime(2^E));
n=p*q;a=3;while(gcd(a^3-a,n)!=1||kronecker(a^2-4,p)!=-1||kronecker(a^2-4,q)!=-1,a++);
e=17;while(gcd(e,(p^2-1)*(q^2-1))!=1,e++));
print("4 keys generated:"gettime());
m=random(2^(2*E))*x+random(2^(2*E));d=lift(Mod(e,(p^2-1)*(q^2-1))^-1);
for(count=1,1000,c=Mod(Mod(1,n)*m,x^2-a*x+1)^e;dm=Mod(Mod(1,n)*c,x^2-a*x+1)^d);
print("1000 Messages:"gettime())}
4 keys generated:18725
1000 Messages:6820;
So, for keys RSA{n-2048, d-2048} and RSA-Frobenius{n-1024, d-2048} the decryption times are twice as long for the latter, but key generation is much quicker for the latter.

The question remains: Are the primes "safe" for the latter?

'nuff said

Last fiddled with by paulunderwood on 2019-04-15 at 23:13
paulunderwood is offline   Reply With Quote
Old 2019-04-16, 00:21   #9
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

3×1,049 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
So, for keys RSA{n-2048, d-2048} and RSA-F
The question remains: Are the primes "safe" for the latter?
With modern key sizes, RSA-1024 or RSA-2048, is it even necessary to use "strong primes" or "safe primes"?

paulunderwood is offline   Reply With Quote
Old 2019-04-16, 04:34   #10
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

13·409 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
With modern key sizes, RSA-1024 or RSA-2048, is it even necessary to use "strong primes" or "safe primes"?
I don't have an answer, but I have asked myself the same question many times. But then I come to the conclusion that since key generation is usually done offline, and rarely changes, then I give up trying to find an answer and just simply use safe/strong primes accordingly and stop worrying about it.
retina is offline   Reply With Quote
Old 2019-04-16, 10:14   #11
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

1100010010112 Posts
Default

Quote:
Originally Posted by retina View Post
I don't have an answer, but I have asked myself the same question many times. But then I come to the conclusion that since key generation is usually done offline, and rarely changes, then I give up trying to find an answer and just simply use safe/strong primes accordingly and stop worrying about it.
I found this 1999 paper by Rivest and RDS, in which it states:

"We argue that contrary to common belief it is unnecessary to use strong primes in the RSA cryptosysytem."
paulunderwood is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Frobenius and semi-prime testing paulunderwood Number Theory Discussion Group 12 2018-11-09 07:07

All times are UTC. The time now is 19:19.

Thu Apr 9 19:19:12 UTC 2020 up 15 days, 16:52, 1 user, load averages: 1.21, 1.45, 1.48

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.