RSA Implemented in PHP

tiberiusx · March 26, 2017

I'm trying to implement a bare-bones RSA encryption protocol in PHP. I'm not very familiar with OOP but tried to implement everything in a class.

I'd love any criticism you have for my OOP use. For example is code like this:

function set_bit_length($bit_length) {
	$this->bit_length = $bit_length;
}

Actually necessary? Couldn't I just manipulate the variable outside of a function? What I've been doing is using $this->variable inside the class and $class->set_variable outside of the class when calling on it. Like I said, not very familiar with OOP, so I don't know best practices.

I tried to write a Extended Euclidean Algorithm to calculate the "inverse mod". It gives the right results, but I'm sure it could be more efficient.

function find_inverse($e, $t) {
	$quot = array();
	$rem = array();
	$s = array(1, 0);
		
	$rem[0] = $e;
	$rem[1] = $t;
		
	// Extended Euclidean Algorithm 
	for ($i = 0; ; $i++) {
		if ($rem[$i + 1] != 0) {
			$quot[$i + 2] = gmp_div_q($rem[$i], $rem[$i + 1]);
			$rem[$i + 2] = gmp_div_r( $rem[$i], $rem[$i + 1]);
			
			$s[$i + 2] = gmp_sub($s[$i], gmp_mul($quot[$i + 2], $s[$i + 1]));
		} else {
			break;
		}
	}
	
	return $s[$i];
}

Also, why is gmp_random depreciated, and how do I implement an alternative?

<?php

class Pencrypt {
	
	// $p - input prime
	// $q - input prime
	// $e - coprime to $n
	var $p;
	var $q;
	var $e;
	var $n;
	var $t;
	
	var $private_key;
	var $public_key1;
	var $public_key2;
	
	var $attempts = 300;
	var $bit_length = 3; # no idea what this value means for gmp_rand
	
	function set_prime($p, $q) {
		$this->p = $p;
		$this->q = $q;
	}
	
	function set_public_key() {
		$this->n = $this->p * $this->q;
		$this->t = ($this->p - 1) * ($this->q - 1);
		
		$this->public_key1 = $this->n;	
	}
	
	function set_bit_length($bit_length) {
		$this->bit_length = $bit_length;
	}
	
	function set_attempts($attempts) {
		$this->attempts = $attempts;
	}
	
	function set_e($e = FALSE) {
		// Check for custom $e value (bug testing)
		if ($e == FALSE) {
			// If $private_key is neg, generate new $e
			do { 
				$this->e = $this->generate_prime($this->bit_length);
				if ($this->e === FALSE) {
					exit("Fatal error: Prime not found. Increase attempts or try again");
					return FALSE;
				}
				$this->private_key = $this->find_inverse($this->e, $this->t);
			} while (gmp_cmp($this->private_key, 0) < 1);
			
			$this->public_key2 = $this->e;
			return TRUE;
		} else {
			$this->e = $e;
			$this->private_key = $this->find_inverse($this->e, $this->t);
			$this->public_key2 = $e;
			return FALSE;
		}
	}
	
	function generate_prime($bits = FALSE) {
		$prime;
		
		if ($bits == FALSE) {
			$bits = $this->bit_length;
		}
	
		// Verify prime probability
		for ($i = 0; $i < $this->attempts; $i++) {
			// Why is gmp_random depreciated? Alternative?
			$prime      = gmp_nextprime(gmp_random($bits)); 
			$safe_prime = gmp_add(gmp_mul($prime, 2), 1);   
			if(gmp_prob_prime($safe_prime)) {                
				break;                                     
			}
			$safe_prime = NULL;                             
		}
		
		if ($safe_prime != NULL) {
			return $prime;
		} else {
			echo "<br /><b>FAILURE</b><br />";
			return FALSE;
		}
		
	}
	
	function find_inverse($e, $t) {
		$quot = array();
		$rem = array();
		$s = array(1, 0);
		
		$rem[0] = $e;
		$rem[1] = $t;
		
		// Extended Euclidean Algorithm 
		for ($i = 0; ; $i++) {
			if ($rem[$i + 1] != 0) {
				$quot[$i + 2] = gmp_div_q($rem[$i], $rem[$i + 1]);
				$rem[$i + 2] = gmp_div_r( $rem[$i], $rem[$i + 1]);
				
				$s[$i + 2] = gmp_sub($s[$i], gmp_mul($quot[$i + 2], $s[$i + 1]));
			} else {
				break;
			}
		}
		
		return $s[$i];
	}
	
	function encrypt($msg) {
		return gmp_powm($msg, $this->e, $this->n);
	}
	
	function decrypt($msg) {
		return gmp_powm($msg, $this->private_key, $this->n);
	}
}

?>

<?php
	set_time_limit(150);
	
	$msg = "171231231344821";
	
	$keys = new Pencrypt();
	$keys->set_attempts(1000);
	$keys->set_bit_length(20);
	$keys->set_prime($keys->generate_prime(), $keys->generate_prime());
	$keys->set_public_key();
	$keys->set_e();
	
	$e_msg = $keys->encrypt($msg);
	echo "Encrypted: " . $e_msg . "<br />";
	
	$d_msg = $keys->decrypt($e_msg);
	echo "Decrypted: " . $d_msg . "<br />";
	
	
	echo "<br /> Logs: <br />";
	echo "<b>p: </b>" . $keys->p . "<br />";
	echo "<b>q: </b>" . $keys->q . "<br />";
	echo "<b>n: </b>" . $keys->n . "<br />";
	echo "<b>t: </b>" . $keys->t . "<br />";
	echo "<b>e: </b>" . $keys->e . "<br />";
	echo "<b>secret key: </b>" . $keys->private_key . "<br />";
?>

Thanks for looking at my code and and help you may have!

Edited March 26, 2017 by tiberiusx

Jacques1 · March 27, 2017

First off: This is just a toy project, right? You're not using this for any actual application?

There are many problems, and I recommend you start with simple classes before jumping to complex ones. Then we don't have to deal with dozens of issues all at the same time.

The syntax you're using is hopelessly outdated, and your naming conventions are nonstandard. This “var” stuff comes from PHP 4; nowadays, we're using the explicit access modifiers private, protected or public (analogous to other OOP languages like Java). Method names use camelCase according to the PSR-1 standard.
Your error handling is weird, to say the least. You abuse booleans to indicate problems, you abuse echo for error messages, and sometimes you kill the entire application. All of this is bad. You need to learn how to use exceptions.
None of your methods performs any kind of validation. You happily accept garbage input and will run into the weirdest problems when you try to use those values.
Your objects aren't properly initialized. After instantiation, they're in a more or less undefined state, and it's up to the user to figure out what they have to do. This is bad. Use the constructor to set required values.
There's currently no documentation whatsoever, which means I have to wade through the entire code to understand what's going on. Use inline documentation in a standard format to explain the classes, attributes and methods (e. g. phpDocumentor).
...

tiberiusx · March 27, 2017

Thank you for taking the time to give those resources. That's exactly the type of criticism I was looking for.

Yes, this is just a pet project. My last experience was programming with PHP 4. I took your suggestions to heart and rewrote my code.

The syntax you're using is hopelessly outdated...

I've renamed the class and methods. There wasn't a convention given for variables. Is $var_name still the normal?

Your error handling is weird, to say the least...

I'm having a little trouble with the logic of Exceptions. When I write:

catch (Exception $exc) {

Is $exc a global variable? Does it just contain an Exception class for that one exception?

If I understand this correctly:

throw new

Will look for the first instance of catch, call the Exception function, and terminate the rest of the function/method?

My question is, why can't I write this:

try {
	// Generate random prime
	$this->e = $this->generatePrime($this->bit_length);
	// Find mod inverse to generate private_key
	$this->private_key = $this->findInverse($this->e, $this->t);
} catch (Exception $exc) {
	echo 'Fatal error: ',  $exc->getMessage(), "\n";
	exit();
}

As this:

// Generate random prime
$this->e = $this->generatePrime($this->bit_length);

// generatePrime() throws an Exception here

// Find mod inverse to generate private_key
$this->private_key = $this->findInverse($this->e, $this->t);

catch (Exception $exc) {
	echo 'Fatal error: ',  $exc->getMessage(), "\n";
	exit();
}

I know the exit() is used wrong, but why do I have to encapsulate everything in a do { } bracket. Why can't I just write my code, and add catches along the way? They have to be bracketed together?

None of your methods performs any kind of validation...

Is it normal to validate every variable? These are not user inputted variables that need to be sanitized, they are only going to be used by the programmer. For example should setBitLength($bit_length) be validated?
Your objects aren't properly initialized...

You're right. I tried to make a __construct() function that made sense, but my class has two optional variables that may or may not be set independently. setPublicKey() does the first real leg work, but it checks the two variables for custom values so can't be the __construct() function.
There's currently no documentation whatsoever...

Thanks for the resource. I've added some more documentation that follows the guidelines. One thing I couldn't find is how to document method variables, like $quot (line 158).

Here is the full rewritten code:

<?php

/**
 * RSA encryption. 
 * 
 * Generates public and private keys, large primes, encrypts and decrypts messages.
 */
class PenCrypt {
	protected $p;
	protected $q;
	protected $e;
	protected $n;
	protected $t;
	
	protected $private_key;
	public $public_key1;
	public $public_key2;
	
	public $attempts = 300;
	public $bit_length = 3; # no idea what this value means for gmp_rand
	
	public function __construct() {
		
	}
	
	/**
	 * Sets p and q or generates a random prime if no value is set
	 *
	 * @param int $p
	 * @param int $q
	 */
	public function setPublicKey($p = NULL, $q = NULL) {
		$this->p = $p;
		$this->q = $q;
		
		// If blank, generate new primes
		try {
			if ($p === NULL)
				$this->p = $this->generatePrime($this->bit_length);
			if ($q === NULL)
				$this->q = $this->generatePrime($this->bit_length);
		} catch (Exception $exc) {
			echo 'Fatal error: ',  $exc->getMessage(), "\n";
			exit();
		}
		
		$this->n = $this->p * $this->q;
		$this->t = ($this->p - 1) * ($this->q - 1);
		
		$this->public_key1 = $this->n;	
	}
	
	/**
	 * Sets bit_length value
	 *
	 * @param int $bit_length
	 */
	public function setBitLength($bit_length) {
		/*if(!is_int($int))
			throw new InvalidArgumentException(
		*/
		$this->bit_length = $bit_length;
	}
	
	/**
	 * Sets number of attempts to try when using generatePrime() 
	 *
	 * @param int $attempts
	 */
	public function setAttempts($attempts) {
		$this->attempts = $attempts;
	}
	
	/**
	 * Generates the private_key
	 *
	 * Generates prime number with generatePrime() then find the mod inverse
	 * with findInverse(). If a custom value is set, that is used instead.
	 *
	 * @param int $e
	 */
	public function setE($e = NULL) {
		// Check for custom $e value
		if ($e === NULL) {
			// If $private_key is neg, generate new $e until positive
			do {
				try {
					// Generate random prime
					$this->e = $this->generatePrime($this->bit_length);
					// Find mod inverse to generate private_key
					$this->private_key = $this->findInverse($this->e, $this->t);
				} catch (Exception $exc) {
					echo 'Fatal error: ',  $exc->getMessage(), "\n";
					exit();
				}
				
			} while (gmp_cmp($this->private_key, 0) < 1);
			
			$this->public_key2 = $this->e;
			
		// If a custom $e value is set
		} else {
			$this->e = $e;
			$this->public_key2 = $e;
			
			// Find mod inverse to generate private_key
			$this->private_key = $this->findInverse($this->e, $this->t);
		}
	}
	
	/**
	 * Generates large prime numbers with GMP
	 *
	 * Currently, sane bit lengths are < 30.
	 *
	 * @param int $bits
	 */
	public function generatePrime($bits = FALSE) {
		$prime = 0;
		
		// Use default bit_length
		if ($bits == FALSE) {
			$bits = $this->bit_length;
		}
	
		// Generate large random prime number
		for ($i = 0; $i < $this->attempts; $i++) {
			// Calc random number $bits long, then find the next prime number
			$prime      = gmp_nextprime(gmp_random($bits)); 
			// Math to ensure primality [?]
			$safe_prime = gmp_add(gmp_mul($prime, 2), 1);   
			// Verify primality, if prime, break from the loop 
			if(gmp_prob_prime($safe_prime)) {                
				break;                                     
			}
			$safe_prime = NULL;                             
		}
		
		if ($safe_prime != NULL) {
			return $prime;
		} else {
			throw new Exception('Could not generate a prime number. Increase the number of attempts or try again.');
		}
		
	}
	
	/**
	 * Find [x] mod inverse of $e and $t
	 *
	 * Uses the Extended Euclidean Algorithm. gmp_invert() also does this,
	 * so this function may be replaced.
	 * $e and $t are numbers, but are stored as GMP objects, not ints.
	 *
	 * @param array $e
	 * @param array $t
	 */
	public function findInverse($e, $t) {
		$quot = array();
		$rem = array();
		$s = array(1, 0);
		
		$rem[0] = $e;
		$rem[1] = $t;
		
		// Extended Euclidean Algorithm 
		for ($i = 0; ; $i++) {
			if ($rem[$i + 1] != 0) {
				$quot[$i + 2] = gmp_div_q($rem[$i], $rem[$i + 1]);
				$rem[$i + 2] = gmp_div_r( $rem[$i], $rem[$i + 1]);
				
				$s[$i + 2] = gmp_sub($s[$i], gmp_mul($quot[$i + 2], $s[$i + 1]));
			} else {
				break;
			}
		}
		
		return $s[$i];
	}
	
	/**
	 * Encrypts a message using power with modulo
	 *
	 * @param string $message
	 */
	public function encrypt($msg) {
		return gmp_powm($msg, $this->e, $this->n);
	}
	
	/**
	 * Decrypts a message using power with modulo
	 * 
	 * @param string $message
	 */
	public function decrypt($msg) {
		return gmp_powm($msg, $this->private_key, $this->n);
	}
}

?>

<?php
	set_time_limit(150);
	
	$msg = "171231231344821";
	
	$keys = new PenCrypt();
	$keys->setAttempts(300);
	$keys->setBitLength(10);
	$keys->setPublicKey();
	$keys->setE();
	
	$e_msg = $keys->encrypt($msg);
	echo "Encrypted: " . $e_msg . "<br />";
	
	$d_msg = $keys->decrypt($e_msg);
	echo "Decrypted: " . $d_msg . "<br />";
?>

Thanks for all your help so far.

Edited March 27, 2017 by tiberiusx

Jacques1 · March 27, 2017

This looks better.

There wasn't a convention given for variables. Is $var_name still the normal?

I would use camelCasel for attributes as well. Two different styles for methods and attributes is a bit odd.

When I write:

catch (Exception $exc) {

Is $exc a global variable? Does it just contain an Exception class for that one exception?

$exc is a variable in the current scope (which may be local or global). It holds an instance of Exception to represent the error that has happened.

If I understand this correctly:

throw new

Will look for the first instance of catch, call the Exception function, and terminate the rest of the function/method?

Yes, an exception causes PHP to jump to the innermost catch block that catches this exception class -- or terminate the entire program if there is no matching catch block.

My question is, why can't I write this:

try {
    // Generate random prime
    $this->e = $this->generatePrime($this->bit_length);
    // Find mod inverse to generate private_key
    $this->private_key = $this->findInverse($this->e, $this->t);
} catch (Exception $exc) {
    echo 'Fatal error: ', $exc->getMessage(), "\n";
    exit();
}

As this:

// Generate random prime
$this->e = $this->generatePrime($this->bit_length);

// generatePrime() throws an Exception here

// Find mod inverse to generate private_key
$this->private_key = $this->findInverse($this->e, $this->t);

catch (Exception $exc) {
    echo 'Fatal error: ', $exc->getMessage(), "\n";
    exit();
}

I know the exit() is used wrong, but why do I have to encapsulate everything in a do { } bracket. Why can't I just write my code, and add catches along the way? They have to be bracketed together?

Because otherwise PHP wouldn't know which statements are supposed to be covered by this exception handler. You can catch exceptions from a single statement or multiple statements, that's why you need to mark them with the try block.

None of your methods performs any kind of validation...

Is it normal to validate every variable? These are not user inputted variables that need to be sanitized, they are only going to be used by the programmer. For example should setBitLength($bit_length) be validated?

Yes, because even programmers make mistakes. Critical features in particular should perform extensive validation to quickly reveal defects and avoid any kind of unwanted operations.

The bit length should be a positive integer. If you already have PHP 7, you can leave the type checks to PHP itself and concentrate on more advanced validations:

// note "int" type hint
public function setBitLength(int $bitLength) {
    if ($bitLength < 0) {
        throw new InvalidArgumentException('The bit length must be positive.');
    }
    // Consider doing more sanity checks: Is the value too low or too high?

    $this->bitLength = $bitLength;
}

Your objects aren't properly initialized...

You're right. I tried to make a __construct() function that made sense, but my class has two optional variables that may or may not be set independently. setPublicKey() does the first real leg work, but it checks the two variables for custom values so can't be the __construct() function.

You can have multiple objects which interact with each other. For example, keys can be represented by a separate RSAPublicKey or RSAPrivateKey class. The instances of those classes are then passed to the encryption/decryption class.

This avoids complex initialization procedures and makes the classes themselves much simpler, because they only have to deal with one specific aspect of RSA.

There's currently no documentation whatsoever...

Thanks for the resource. I've added some more documentation that follows the guidelines. One thing I couldn't find is how to document method variables, like $quot (line 158).

Local variables aren't formally documented (you can use standard comments, though).

You should document attributes, though. And add descriptions to method parameters to explain their purpose (unless it's absolutely clear).

Edited March 27, 2017 by Jacques1

Jacques1 · March 27, 2017

As to the new code:

Never ever catch exceptions only to print the error message on the screen. Not even for testing. This completely defeats the purpose of exceptions, because now you have the same bad error handling procedure as before. If you cannot handle the exception in a meaningful way, just leave it alone. PHP itself will terminate the program and send the complete error information (not just the message!) to the right target.
When you do catch exceptions, then catch specific classes, not just the generic Exception.
Public attributes make it impossible to perform validation, so you shouldn't have them.
You should also document return values and exceptions.

Sign In

RSA Implemented in PHP

Recommended Posts

tiberiusx

Link to comment

Share on other sites

Jacques1

Link to comment

Share on other sites

tiberiusx

Link to comment

Share on other sites

Jacques1

Link to comment

Share on other sites

Jacques1

Link to comment

Share on other sites

Join the conversation

Browse

Activity

Important Information