mersenneforum.org > Math RSA on Frobenius
 Register FAQ Search Today's Posts Mark Forums Read

 2019-03-28, 20:50 #1 paulunderwood     Sep 2002 Database er0rr 23×32×53 Posts 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
 2019-03-29, 13:19 #2 Dr Sardonicus     Feb 2017 Nowhere 10010110111112 Posts 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
 2019-03-29, 15:05 #3 ATH Einyen     Dec 2003 Denmark 3×5×211 Posts 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?
2019-03-29, 16:27   #4
Nick

Dec 2012
The Netherlands

2·3·7·41 Posts

Quote:
 Originally Posted by ATH 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\}$$.

2019-04-03, 18:44   #5
paulunderwood

Sep 2002
Database er0rr

EE816 Posts

Quote:
 Originally Posted by Dr Sardonicus 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.

2019-04-04, 10:44   #6
paulunderwood

Sep 2002
Database er0rr

23×32×53 Posts

Quote:
 Originally Posted by paulunderwood 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

2019-04-15, 14:54   #7
paulunderwood

Sep 2002
Database er0rr

23·32·53 Posts

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

2019-04-15, 22:44   #8
paulunderwood

Sep 2002
Database er0rr

23·32·53 Posts

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

2019-04-16, 00:21   #9
paulunderwood

Sep 2002
Database er0rr

EE816 Posts

Quote:
 Originally Posted by paulunderwood 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"?

2019-04-16, 04:34   #10
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

2×31×101 Posts

Quote:
 Originally Posted by paulunderwood 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.

2019-04-16, 10:14   #11
paulunderwood

Sep 2002
Database er0rr

1110111010002 Posts

Quote:
 Originally Posted by retina 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."

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

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

Fri Sep 24 19:20:39 UTC 2021 up 63 days, 13:49, 1 user, load averages: 2.04, 1.98, 1.87