Here is an attempt to leverage Java's BigInteger class to implement the RSA algorithm, as well as md5 and sha512 hashing functions to generate keys for what I hope to be strong cryptography. My prayer is that some of my ideas are novel and not just wrong.
- This is a test, this is only a test. 'Keys' are generated, the message is encrypted, displayed, decrypted, displayed, and all tossed out with the bathwater.
- This implementation ignores salting. I suppose my thought here is that computational complexity (time) and memory requirements for a large enough key would dissuade an adversary from successfully utilizing a rainbow table.
- I understand using a sieve of Eratosthenes to pick out a value for e is overkill, expensive, and could be functionally reproduced here by taking a pseudo-random number and finding
nextProbablePrime(). I've included it hoping to get feedback on this implementation. - I am a total novice. I was a New Media major. I want to learn. I humbly request any time and thoughts you wish to impart. Running time is ~1m; half due to the sieve, half for the 1000 iterations of
nextProbablyPrime().
RSATest.java: (Usage: java RSATest "some password" "some message")
import java.math.BigInteger;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
public class RSATest {
//seive array for lower 2b primes
public static byte[] a = new byte[(Integer.MAX_VALUE/20)+1];
public static BigInteger p=BigInteger.ONE,q=BigInteger.ONE,t;
public static MessageDigest sha,md5;
public static int lp = 3; // last prime sieved
//method returns prime number after hash with given digest
public static BigInteger h(byte[] ba, MessageDigest md){
BigInteger t=(new BigInteger(md.digest(ba))).abs().nextProbablePrime();
md.update(t.toByteArray());
return t;
}
public static void main(String[] args) {
BigInteger e,n,t,d,sec,cy,dec;
byte[] a,ar;
String secret;
int itr, itr2; //itr: iterations
if(args.length!=2){
System.out.println("HELP - parameters: \"password\" \"message\"");
System.exit(1);
}
secret=args[1];
//TODO: reject palindromes?
a=args[0].getBytes();
ar = (new StringBuilder(args[0])).reverse().toString().getBytes();
//init sha and md5 digest methods with string
try {
sha = MessageDigest.getInstance("SHA-512");
sha.update(a);
md5 = MessageDigest.getInstance("MD5");
md5.update(a);
} catch (NoSuchAlgorithmException ex) {
ex.printStackTrace();
System.exit(0);
}
//generate primes from hash of string and its reverse
p=p.multiply(h(a,sha)).nextProbablePrime();
p=p.multiply(h(a,md5)).nextProbablePrime();
p=p.multiply(h(ar,sha)).nextProbablePrime();
p=p.multiply(h(ar,md5)).nextProbablePrime();
sha.update(p.toByteArray());
md5.update(p.toByteArray());
q=q.multiply(h(ar,sha)).nextProbablePrime();
q=q.multiply(h(ar,md5)).nextProbablePrime();
sha.update(q.toByteArray());
md5.update(q.toByteArray());
q=q.multiply(h(a,sha)).nextProbablePrime();
q=q.multiply(h(a,md5)).nextProbablePrime();
//increase computational time and ensure primality of p/q
itr = p.mod(BigInteger.valueOf(1000)).intValue();
itr2 = 1000-itr;
for(int i = 1;i<itr;i++)p=p.nextProbablePrime();
for(int x = 1;x<itr2;x++)q=q.nextProbablePrime();
while(!p.isProbablePrime(Integer.MAX_VALUE))p=p.nextProbablePrime();
while(!q.isProbablePrime(Integer.MAX_VALUE))q=q.nextProbablePrime();
System.out.println("P:"+p.toString(10));
System.out.println("Q:"+q.toString(10));
//for exponent
//aquire one of the lower primes using sieve
//pseudo random prime between 7 and int max
si(p.mod(BigInteger.valueOf(Integer.MAX_VALUE)).intValue());
e = BigInteger.valueOf(lp);
//rsa encrypt and decrypt
n = p.multiply(q);
t = p.subtract(BigInteger.ONE).multiply(q.subtract(BigInteger.ONE));
d = e.modInverse(t);
sec = new BigInteger(secret.getBytes());
//cypher text
cy = sec.modPow(e,n);
System.out.println("C:"+cy.toString(16));
//decrypted text
dec = cy.modPow(d,n);
System.out.println("D:"+(new String(dec.toByteArray())));
}
//sieve of eratosthenes
public static void si(int max){
s(3);
s(7);
for(int i=11;i<max;i+=10){
if(t(i))s(i);
if(0<(i+2)&&t(i+2))s(i+2);
if(0<(i+6)&&t(i+6))s(i+6);
if(0<(i+8)&&t(i+8))s(i+8);
}
}
//get test bit from sieve
public static boolean t(int i){
return (a[i/20]&b(i))==0;
}
//int value to bit mask used in sieve
public static byte b(int i){
return (byte)(1<<(((i%20)/2)-((i%20)/5)+((i%20)/10)));
}
//sieve forward prime value i
public static void s(int i) {
lp=i;for(int w=3*i;w>0;w+=(((w+i+i)%5)==0?4*i:2*i))a[w/20]|=b(w);
}
}
Is there any value here? My ambition is to understand the computational and cryptographic theory and translate this into best practices. I apologize for the terrible naming of variables and methods, heinous runtime, useless commenting, unnecessary golfing, and using spaces over tabs.
Example output:
>java RSATest "password" "test"
P:10090275631957288744610599659040664305405434722352094636668421960416506099994666827664511624543986219997911864288607312795882978242921884901347541608283715814165727102775081158850275803219608306098677869589957898032998379673745817876752829320076809618549060139888917446177159027216418146574898873844039044426500320311838804799370581535223413777861948749552759092994514733751610983813
Q:5425365986445829161530505882662909832813406327751968505626162017780151029106074817664839063991268038579259781345806774068118642908105542837724653877104358137779083102271171002417267868641163457971958213047417570560412152250447538894719454784926316581576607321753609289397778946058304937920474724957098706683798464369444644490724812822892582670707683075052137846220273984681853710951
C:105ed567b39e1a87f8c1a3cb370bb528da8a12e69a93d691a5f5ac18d1af691d129f660b4e730eaa9a16c548e20281730ebbad1485a4b4ce79d13061926bc513c66515c5dab3c8e15af2075546abd57814a53876fa113c4d1ae67b63c6e7bf16babde1c85b4ac02c5c23b296accb4836558dcd8b2c66865c6ed027dbfecd4f0f544d14d441c2c73b13bc43269b0ffd9a068f2a5a068b521aff9ba545efa01642df749a5bb639771d7d5c20d6edd23f4739640e5d63eecf3227c2157bfa391a6e617a4049cd3dc84f455933d75cd51a97fd9c7493eb52436be866a909ff6bb598306ec7cfb0ab49551e6e11ca7183a346740ae469545a9237ce201fe4f93d82dbe1ef795e39ea37a154b6c5027e76644d2a250c43363dc0e56addaac3f2e1a343429ffc7ede3144ad822ae4022ba5b1f704c8374fc220fed38c6094e59a
D:test
h(a,sha)could bebigIntFromHashedStringWithMsgDigest(inputPassword,sha512msgDigest)and I would have to breakp=p.multiply(h(a,sha)).nextProbablePrime();into multiple lines to avoid wrapping over 80 characters. This would obfuscate the important ways these highly repetitive lines differ. \$\endgroup\$hprobably would beHashToPrime. e also doesn't need to be prime, incrementing it until its gcd with (p-1)(q-1) is 1 will do (while starting at 3). Also this search strategy for p and q is somewhat unneccessarily complex (more usual would be to generate a large random buffer, convert to integer and then take the next prime). \$\endgroup\$