0

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;
}
  • 2
    You can find sample steps in Cryptography – kelalaka Jan 24 at 13:59
  • 5
    why are you creating RSA from scratch? – schroeder Jan 24 at 14:01
  • 1
    @schroeder Given that p and q are trivial values in his code, I imagine it's an assignment. – forest Jan 25 at 4:28
2

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:

enter image description here

That being said, as @Sjoerd pointed out, the values 3 and 65537 are commonly used for e. [1]

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:

enter image description here

To make things easier, you should use the modular multiplicative inverse of e.

enter image description here

  • You may want to point out that you can find the modular inverse using the extended Euclidean algorithm. – forest Jan 25 at 4:29
1

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.