20190328, 20:50  #1 
Sep 2002
Database er0rr
2·7·281 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 = m_{1}x + m_{2} to the cipher number c = m^e (mod n, x^2a*x+1) for some a: 2<a<(n2). (m_{1} non zero.) To decipher compute c^d (mod n, x^2a*x+1). Because exponentiation over x^2a*x+1 in ~2 log_{2} 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 20190328 at 21:01 
20190329, 13:19  #2 
Feb 2017
Nowhere
1010000001011_{2} 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 p1. Similarly for q. There are several possible cases. I suppose gcd(a^2  4, n) should be checked for the sake of thoroughness :D 
20190329, 15:05  #3 
Einyen
Dec 2003
Denmark
C7E_{16} 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^2a*x+1) What is the definition of a number mod 2 different numbers? 
20190329, 16:27  #4  
Dec 2012
The Netherlands
2·3·293 Posts 
Quote:
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,n1\}\). 

20190403, 18:44  #5  
Sep 2002
Database er0rr
2·7·281 Posts 
Quote:


20190404, 10:44  #6  
Sep 2002
Database er0rr
2·7·281 Posts 
Quote:
I suppose gcd(a^3  a, n) would also be wise to check. Last fiddled with by paulunderwood on 20190404 at 10:57 

20190415, 14:54  #7  
Sep 2002
Database er0rr
2·7·281 Posts 
I ran a couple of naive timing tests on RSA and RSAFrobenius. Both use "safe primes" w.r.t (p1)*(q1). That is both (p1)/2 and (q1)/2 are prime. But should RSAfrobenius be using "extra safe primes" w.r.t. (p^21)*(q^21)?
RSA: Code:
gettime();E=512;for(count=1,10,m=random(2^(2*E)); p=randomprime(2^E);while(!ispseudoprime((p1)/2),p=randomprime(2^E)); q=randomprime(2^E);while(!ispseudoprime((q1)/2),q=randomprime(2^E)); n=p*q;e=17;d=lift(Mod(e,(p1)*(q1))^1);c=Mod(m,n)^e;dm=Mod(c,n)^d); gettime() 35713 Code:
gettime();E=512;for(count=1,10,m=random(2^(2*E))*x+random(2^(2*E)); p=randomprime(2^E);while(!ispseudoprime((p1)/2),p=randomprime(2^E)); q=randomprime(2^E);while(!ispseudoprime((q1)/2),q=randomprime(2^E)); n=p*q;a=3;while(gcd(a^3a,n)!=1 kronecker(a^24,p)!=1kronecker(a^24,q)!=1,a++); e=17;while(gcd(e,(p^21)*(q^21))!=1,e++); d=lift(Mod(e,(p^21)*(q^21))^1); c=Mod(Mod(1,n)*m,x^2a*x+1)^e;dm=Mod(Mod(1,n)*c,x^2a*x+1)^d);gettime() 38840 So with one key generation and 10 messages or 20 in the case with RSAFrobenius: RSA: Code:
gettime();E=512; p=randomprime(2^E);while(!ispseudoprime((p1)/2),p=randomprime(2^E)); q=randomprime(2^E);while(!ispseudoprime((q1)/2),q=randomprime(2^E));n=p*q;e=17;d=lift(Mod(e,(p1)*(q1))^1); for(count=1,10,m=random(2^(2*E));c=Mod(m,n)^e;dm=Mod(c,n)^d);gettime() 15232 Quote:
Another test with the same key generation: Code:
ettime();E=512; p=randomprime(2^E);while(!ispseudoprime((p1)/2),p=randomprime(2^E)); q=randomprime(2^E);while(!ispseudoprime((q1)/2),q=randomprime(2^E));n=p*q;a=3; while(gcd(a^3a,n)!=1kronecker(a^24,p)!=1kronecker(a^24,q)!=1,a++);e=17; while(gcd(e,(p^21)*(q^21))!=1,e++);print(gettime()); for(count=1,100,m=random(2^(2*E))*x+random(2^(2*E));d=lift(Mod(e,(p^21)*(q^21))^1);c=Mod(Mod(1,n)*m,x^2a*x+1)^e;dm=Mod(Mod(1,n)*c,x^2a*x+1)^d);print(gettime()); d=lift(Mod(e,(p1)*(q1))^1);for(count=1,100,m=random(2^(2*E));c=Mod(m,n)^e; dm=Mod(c,n)^d);gettime() 1573 684 64 So final test: same key sizes and a 100 messages for RSA and 200 messages for RSAFrobenius: RSA: Code:
gettime();E=1024; p=randomprime(2^E);while(!ispseudoprime((p1)/2),p=randomprime(2^E)); q=randomprime(2^E);while(!ispseudoprime((q1)/2),q=randomprime(2^E)); n=p*q;e=17;d=lift(Mod(e,(p1)*(q1))^1); for(count=1,100,m=random(2^(2*E));c=Mod(m,n)^e;dm=Mod(c,n)^d);gettime() 69953 Code:
gettime();E=512; p=randomprime(2^E);while(!ispseudoprime((p1)/2),p=randomprime(2^E)); q=randomprime(2^E);while(!ispseudoprime((q1)/2),q=randomprime(2^E)); n=p*q;a=3;while(gcd(a^3a,n)!=1kronecker(a^24,p)!=1 kronecker(a^24,q)!=1,a++);e=17;while(gcd(e,(p^21)*(q^21))!=1,e++); for(count=1,100,m=random(2^(2*E))*x+random(2^(2*E)); d=lift(Mod(e,(p^21)*(q^21))^1);c=Mod(Mod(1,n)*m,x^2a*x+1)^e;dm=Mod(Mod(1,n)*c,x^2a*x+1)^d);gettime() 2044 Last fiddled with by paulunderwood on 20190415 at 15:52 

20190415, 22:44  #8  
Sep 2002
Database er0rr
2×7×281 Posts 
Key generation is very timeconsuming. Here I compare 2048 bit messages with ~2048 bit decryption keys:
RSA2048: Code:
{gettime();E=1024;for(count=1,4 ,p=randomprime(2^E);while(!ispseudoprime((p1)/2),p=randomprime(2^E)); q=randomprime(2^E);while(!ispseudoprime((q1)/2),q=randomprime(2^E)); n=p*q;e=17;d=lift(Mod(e,(p1)*(q1))^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 Quote:
The question remains: Are the primes "safe" for the latter? 'nuff said Last fiddled with by paulunderwood on 20190415 at 23:13 

20190416, 00:21  #9 
Sep 2002
Database er0rr
111101011110_{2} Posts 

20190416, 04:34  #10 
Undefined
"The unspeakable one"
Jun 2006
My evil lair
2·23·137 Posts 
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.

20190416, 10:14  #11  
Sep 2002
Database er0rr
2·7·281 Posts 
Quote:
"We argue that contrary to common belief it is unnecessary to use strong primes in the RSA cryptosysytem." 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Frobenius and semiprime testing  paulunderwood  Number Theory Discussion Group  12  20181109 07:07 