# Understanding RSA key generation and implementation in Java

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.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
D:test

• Why do you use this unnecessary golfing and the terrible variable names? If you don't have good reason to do so, you should clean up your code before the first review comes in. There's more interesting things to comment about than bad names and unreadable code. – Roland Illig Nov 11 '19 at 17:31
• You are likely correct, but to answer your question, this formatting allows me to understand and hold the code in my mind better, with condensed functional blocks rather than being able to read it like a book. I find the extra white space and verbosity to be excessive and it gives me buffer overflow. h(a,sha) could be bigIntFromHashedStringWithMsgDigest(inputPassword,sha512msgDigest) and I would have to break p=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. – Jonathan Nov 11 '19 at 18:41
• h probably would be HashToPrime. 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). – SEJPM Nov 11 '19 at 22:25
• @SEJPM, thank you. Regarding P's and Q's, I suppose I could seed a pseudo-random number generator based on the argument given and maintain a deterministic outcome. The unnecessary complexity here is perhaps a misguided attempt on my part to create some distance from the output of extremely fast algorithms (sha/md5) to pad what may be a fairly weak input. – Jonathan Nov 11 '19 at 23:18
• Thanks for explaining why this programming style makes sense to you. I had just been confused because you apologized. Since the style makes sense to you and is required for you to read the code efficiently, you could just explain exactly this in the question. I can accept many styles as correct, I just need to know that they are intentional. – Roland Illig Nov 12 '19 at 0:40

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.

If you start at cryptography, you should not start by making up your own schemes and hoping that they are correct. And you should write a paper in case you want to test your scheme, and clearly describe your goals and techniques. A code review is not what is expected for new schemes.

I apologize for the terrible naming of variables and methods, heinous runtime, useless commenting, unnecessary golfing, and using spaces over tabs.

No, that's not how you develop. You should correctly name your variables, perform your spacing etc. when writing the program. Don't expect you get time to polish up your "proof of concept" and always expect that you need to share your code with others, if just to ask questions or to make sure it is readable after you've checked it into a shared code repository / versioning system such as Git.

Personally I prefer spaces over tabs, especially since that's more compatible with e.g. Markdown and other tools that expect text / disrespect tabs.

//seive array for lower 2b primes


Do a spellcheck or use an IDE that does this.

  public static byte[] a = new byte[(Integer.MAX_VALUE/20)+1];


What is a? What is this 20? What is 1? Why is a not a constant, written as A?

  public static BigInteger p=BigInteger.ONE,q=BigInteger.ONE,t;


Statics are supposed to be constants. Don't use more than one statement per line unless there is a compelling reason to do otherwise. t is especially hidden here.

  public static MessageDigest sha,md5;


You later use these instances to hide program state, don't do that.

  public static int lp = 3; // last prime sieved


Place comments before the line, as they may disappear if you e.g. refactor the name lp into something that makes sense.

  public static BigInteger h(byte[] ba, MessageDigest md){


ba is not a good name as it doesn't tell what ba is used for. seed would probably be a better name.

    BigInteger t=(new BigInteger(md.digest(ba))).abs().nextProbablePrime();


So you use a hash, then abs (probably not knowing about new BigInteger(1, byte[]) and then go for nextProbablePrime, using ba for the entropy required to create a random prime. Ugh.

    md.update(t.toByteArray());


Then, using a static method, you have an undocumented side effect in md, storing the state in a globally accessible class variable. Bad stuff all round.

    BigInteger e,n,t,d,sec,cy,dec;
byte[] a,ar;
String secret;
int itr, itr2; //itr: iterations


In Java, you declare the variables when you use them, not before, minimizing scope and therefore state you have to keep track of.

    secret=args[1];


A string is not a secret but a password.

    a=args[0].getBytes();


Here a depends on the platform default encoding, which differs in Java. Known bad practice.

        sha = MessageDigest.getInstance("SHA-512");
sha.update(a);
md5 = MessageDigest.getInstance("MD5");
md5.update(a);


Absolutely unclear why you need two hashes, and why you would ever use MD5 for anything new.

    //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();


Great, now we have got no idea what is hashed or not, and it is not documented. Besides that, we call nextProbablePrime() as if it is a computationally efficient operation, which it definitely is not. As the input is only the amount of bytes in the hash operation, the result will be a list of tiny primes. Not useful at all. The variable reuse is horrid as well.

    //increase computational time and ensure primality of p/q
itr = p.mod(BigInteger.valueOf(1000)).intValue();


Why would you ever want to increase computation time? What are you trying to strengthen? What use is it if the result is only in the range 0..999, something that can be easily brute forced?

    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();


Whatever. Why?

Got bored. Encryption and decryption (using raw, insecure RSA) in the same method. Trash programming, no clear description. Exceptionally bad exception handling. The variable secret holds the plaintext, normally I would stop reading at that.

Don't see any "meat" in there because I have no idea what you are even trying to accomplish.

Start by learning cryptography and take a few lessons in structured programming. Then Effective Java and a style guide or two. Start over and post again when you're done, because this should put some blushes on your face. If it doesn't now, it will when you've studied these fields. You are just not ready what you've tried in the question.

• I appreciate that you took the time. I'll clarify the sparse bits, so you can see what is happening. A password is taken from standard in and the reverse is also stored. Both are hashed two ways; all four results used to index two deterministic pseudo-random primes, p and q; which are stepped forward another 1000 slow iterations. These values are used to test something equivalent to RSA. Separately, a byte-packed sieve for integer primes ending in 1,3,7, and 9. A) by using modInverse and modPow of BigInteger am I implementing RSA and B) what do you think of this sieve over the int space? – Jonathan Jan 14 '20 at 20:56
• I'm not the best person to answer that question. It seems to me that you do a lot of "slowing down", but if the end result is that p and q are on the small side then all seems for nought to me. You need to formally describe your goals, the algorithm, and the perceived attacks and how those are averted. Before that, asking for a review of the scheme is not going to get any serious reactions (well, unless you are lucky, there is always that possibility). – Maarten Bodewes Jan 14 '20 at 21:37
• P and Q are roughly in the order of twice the bits of the sha and md5 hashes put together. The only small-ish values are the number of iterations each are stepped forward within the set of primes to prevent a table-based attack and the prime value chosen for exponentiation, which is not a fixed value here. – Jonathan Jan 14 '20 at 22:14
• Even if you combine MD5 and SHA-512 output bit sizes, you would still only have 128 + 512 = 640 bits. That's very far from secure for either the DL or RSA problem, so you would have to somehow prove that your scheme is secure. Saying that 640 bits is enough for everyone is not going to cut it, RSA has already been broken for such key sizes. And RSA generally requires primes that are in the same ballpark w.r.t. the number of bits. "Smallish" for RSA is still huge in human scale. – Maarten Bodewes Jan 14 '20 at 22:21
• PQ is greater than 2500 bit – Jonathan Jan 14 '20 at 22:39