Crypto codes: GGH public key cryptosystem

Download code from here
I only did the decryption part, using Babai's algorithm (for homework :D)

Crypto codes: Elliptic ElGamal

Download code from here

Crypto codes:Miller Rabin Primality test

Download code from here

Output: (exercise 3.14 in the Introduction of Mathematical Cryptography)

1105 is composite with witness 2
294409 is composite with witness 2
118901509 is prime
118901521 is composite with witness 2
118901527 is prime
118915387 is composite with witness 2

Crypto codes: Elliptic curve cryptography

Download code from here
Code includes:
Elliptic curve addition,
Point in Elliptic curve over finite fields
double-and-add algorithm for Elliptic curves

Output:

Points in E(F13) are :
(-Infinity,-Infinity)
(1.0,5.0)
(1.0,8.0)
(2.0,3.0)
(2.0,10.0)
(9.0,6.0)
(9.0,7.0)
(12.0,2.0)
(12.0,11.0)
Addition test->
(9.0,7.0) + (1.0,8.0) =(2.0,10.0)
double-and-add algorithm for elliptic curve->
947*(6.0,730.0) mod 3623= (3492.0,60.0)

Crypto codes: Pollard’s p − 1 factorization algorithm

Code here
It uses prime factor code from square root

Output shows the steps of the algorithm with results:

Find prime factors of 48356747:
2^19! -1 = 13944673 (mod 48356747)
gcd(2^19!-1,48356747) = 6917
factors of 48356747, p=6917, and q=48356747/6917=6991
The prime factorization of 6916 is: 2, 2, 7, 13, 19

The prime factorization of 6990 is: 2, 3, 5, 233

Crypto codes: Square roots modulo composite moduli

Chinese remainder code: Here
Fast squaring code: Crypto codes 1


Square roots modulo composite moduli: Download from here

Crypto codes (3)

Download from here
For the inverse and fast squaring code, see Crypto codes: 1

Finds eth root modulo p:

public class RSA {

 //find x from x^e = c (mod p)
  public static long findRoot(long e, long c, long p)
  {
   long x = 0;
   
   //find e^-1 (mod p-1)
   long eInverse = crypto.inverse(p-1, e);
   
   //x = c^d (mod p)
   x = crypto.fastSq(p, c, eInverse);
   
   return x;
  }
       //test: answer = 6059
  public static void main(String[] args) {
   
      long e = 1583;
      long c = 4714;
      long p = 7919;
      
   long x = RSA.findRoot(e,c, p);
   System.out.println("Solution to x^"+e+" = "+c+" (mod "+p+"): x= "+x);
  }

}

This test will return:

Solution to x^1583 = 4714 (mod 7919): x= 6059

Matlab codes: http://www-users.math.umd.edu/~lcw/MatlabCode/

Crypto codes: Chinese remainder theorem

For gcd and inverse code, see Crypto codes

Java implementation of Chinese remainder theorem, download from here
Matlab code here

For this particular example, output will look like the following:

Step:0->x=2+3*5=17
Step:1->x=17+21*7=164
Solution:164

Crypto codes: ElGamal public key cryptosystem

Algorithms from An Introduction to Mathematical Cryptography book.
Here, Bob sends an encrypted message to Alice using ElGamal public key cryptosystem.
Download code from here

Extended Euclidean algorithm
Matlab code for modular inverse:

[u,y,d] = gcd(x,p); 
y = mod(y,p);