-
-
Save ModsByMorgue/6a86e0cb3c4ef2f5c958aaa46631553e to your computer and use it in GitHub Desktop.
Java RSA
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import java.math.BigInteger; | |
| import java.security.SecureRandom; | |
| import java.util.Arrays; | |
| import java.util.Random; | |
| import static java.math.BigInteger.ONE; | |
| public class RSA { | |
| public static void main(String[] args) { | |
| // https://simple.wikipedia.org/wiki/RSA_(algorithm) | |
| // Key generation | |
| // ============== | |
| // 1. Choose two different large random prime numbers p and q | |
| int bitLength = 128; | |
| Random rnd = new SecureRandom(); | |
| BigInteger p = BigInteger.probablePrime(bitLength, rnd); | |
| BigInteger q = BigInteger.probablePrime(bitLength, rnd); | |
| // 2. Calculate {@code n = p q} (n is the modulus for the public key and the private keys) | |
| BigInteger n = p.multiply(q); | |
| // 3. Calculate the totient {@code phi(n) = (p-1)(q-1)} | |
| BigInteger phi = (p.subtract(ONE)).multiply(q.subtract(ONE)); | |
| // 4. Choose an integer e (the public key exponent) such that {@code 1 < e < phi} and e is coprime to phi | |
| BigInteger e = BigInteger.valueOf(65537); | |
| if (!e.isProbablePrime(100)) throw new IllegalArgumentException("e must be prime"); | |
| if (e.compareTo(phi) == 1) throw new IllegalArgumentException("e too large - use a smaller value or increase the bitLength"); | |
| // 5. Compute d (the private key exponent) to satisfy congruence relation {@code de = 1 (mod phi(n))} | |
| BigInteger d = e.modInverse(phi); | |
| // The public key is made of the modulus n and the public (or encryption) exponent e. | |
| // The private key is made of the modulus n and the private (or decryption) exponent d which must be kept secret. | |
| System.out.println("p = " + p); | |
| System.out.println("q = " + q); | |
| System.out.println("n = " + n); | |
| System.out.println("phi = " + phi); | |
| System.out.println("e = " + e); | |
| System.out.println("d = " + d); | |
| // Encrypting a message | |
| // ==================== | |
| // Alice gives her public key (n and e) to Bob and keeps her private key secret. | |
| // Bob wants to send message M to Alice. | |
| String M = "Hello world"; | |
| System.out.println("M = " + M); | |
| // First he turns M into a number m smaller than n | |
| BigInteger m = new BigInteger(M.getBytes()); | |
| if (m.compareTo(n) == 1) throw new IllegalArgumentException("message too long - increase bitLength or split the message"); | |
| // He then computes the ciphertext c corresponding to: {@code c = m^e mod n} | |
| byte[] c = m.modPow(e, n).toByteArray(); | |
| System.out.println("c = " + Arrays.toString(c)); | |
| // Decrypting a message | |
| // ==================== | |
| // Alice can recover m from c by using her private key d in the following procedure: {@code m = c^d mod n}. | |
| BigInteger decrypted_m = (new BigInteger(c)).modPow(d, n); | |
| String decrypted_M = new String(decrypted_m.toByteArray()); | |
| System.out.println("decrypted_M = " + decrypted_M); | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment