# RSA generating private and public keys

I'm trying to implement RSA encryption in PHP. I'm stuck at generating the public and private keys.

I have `P = 61`, `Q = 53`, `MOD = P * Q = 3233`, `N = (Q - 1) * (P - 1) = 3120`. How do I chose the value of `e` after computing all GCD values?

``````function generatePublicKeyValue(\$n){
\$n2 = 0;
for( \$i2 = 1; \$i2 < \$n;\$i2++ ){
if( gratestCommonDivisor(\$i2,\$n) == 1  ){
if( \$i2 > 1 ){
\$n2 = \$i2;
return \$n2;
}
}
}
}
``````

How do I calculate the private key knowing the value of `N` and `e`?

``````function generatePrivateKeyValue(\$n,\$e){
\$d =  ( 2 * \$n +1) / \$e ;
return \$d;
}
``````
• You can find sample steps in Cryptography – kelalaka Jan 24 '19 at 13:59
• why are you creating RSA from scratch? – schroeder Jan 24 '19 at 14:01
• @schroeder Given that p and q are trivial values in his code, I imagine it's an assignment. – forest Jan 25 '19 at 4:28

I am assuming you are aware that this is text-book RSA and you are not planning on implementing this for security purposes. In case this is not clear, let me just remind you that you should not roll your own crypto for anything security related.

Now with that aside, I will try my best to answer your questions. Please excuse the use of images for formulas. Unfortunately, this website does not have LaTeX support.

How do I chose the value of "e" after computing all GCD values?

I will rename your variables as follows: `p = 61`, `q = 53`, `n = p * q = 3233`, and `phi(n) = (q - 1) * (p - 1) = 3120`, where `phi()` is Euler's totient function, denoted as `φ(n)` in my LaTeX snippets. With these variables you can pick a value for `e` as follows: That being said, as @Sjoerd pointed out, the values 3 and 65537 are commonly used for `e`. 

How do I calculate the private key knowing the value of N and "e"?

To compute the private key `d`, use the following congruence equation and solve for `d`: To make things easier, you should use the modular multiplicative inverse of `e`. • You may want to point out that you can find the modular inverse using the extended Euclidean algorithm. – forest Jan 25 '19 at 4:29

e is typically a fixed prime number, such as 3 or 65537. Since you are working with small numbers, using 3 as value for e would be logical.

Once you have e, you calculate d=e-1 mod λ(n). The calculation e-1 is often called the modular inverse, and you can find code examples in PHP for this.

Maybe you can take a look at phpseclib createKey function as an example.