Simple cryptography problem to be implemented in PHP

Question

I need to implement a couple of functions which comply with the following:

1. function genKey: given a string q (this may be a MD5 or SHA hash) and a seed string, the function must generate a new string p

2. function checkKey: this function must return true if a string p was generated from string q (using the previous function)

In seudo-code the above would be something lie this:

p=genKey(q,seed) ; // generate string p from q and seed 

checkKey(p,q)==true ; // if p was generated from q, then this must return true. False otherwise.

Does anyone know about existing algorithms that do such thing??
I can implement the algorithms myself if there are no known implementations for PHP, so what I'm really asking is for the procedure to accomplish this.

Answer 1

You can use either crypt(), hash(), or md5().

Edit: I don't mind the downvote. Looking at the complexity of the other answers, I must have misinterpreted the question. But it would be nice if people would accompany their downvotes with a comment so that I at least know what is wrong with my answer.

What I gleaned from the question is that the questioner wants to implement something like:

function genKey($q, $seed) {
  // assuming $seed is a properly formatted md5/sha salt
  return crypt($q, $seed);
}

function checkKey($p, $q, $seed) {
  return ($p == genKey($q, $seed));
}

Am I wrong in thinking that any one of PHP's one-way encryption functions can be used to accomplish this?

Answer 2

Will the checking side have access to seed? If seed can be kept secure on the checking side (like on a web app) you could easily do something like HTTP Digest authentication does using MD5.

Pseudocode:

   function genKey(q) {
      p = md5sum(q . ':' . seed);
      return p;
   }

   function checkKey(p,q) {
      return md5sum(q . ':' . seed) == p;
   }

If you need a second party to verify the "signature" then you'll probably just want to use PKI.

Answer 3

For this discussion let p == hash(q)

You could then easily use OpenSSL with php to sign 'p' with a private key and keep that signature along side 'p'.

It is then simple to use the OpenSSL verify function to check 'p' against the signature using the public key that is paired with your private key. In this case 'p' would be the data to verify.

See openssl_sign and openssl_verify for info and examples of using OpenSSL in php to sign and verify data:

Answer 4

You could try something like this:

$p = genKey($q,rand());
checkKey($p,$q) == true;


function genkey($q,$seed)
{
    if(array_search($_SESSION['seeds'],$seed) === FALSE)
    {
        $_SESSION['seeds'][] = $seed;
    }
    return hash("sha512", $q . $seed);
}

function checkKey($p,$q)
{
    $returnVal = false;
    foreach($_SESSION['seeds'] AS $s)
    {
        if(hash("sha512", $q . $s) == $p)
        {
            $returnVal = true;
            break;
        }
    }
    return $returnVal;
}

Of course, I would recommend something else for storage of valid seeds, but this is just a proof of concept.

Answer 5

Okay, what you are referring to is a principle of public key cryptography, specifically creating signatures. It runs along complex mathematic principles (which you would have to implement).

In basic RSA signatures, you create a signature s by applying the following math:

s = m^d % n

Where m is the message (or string q for you), d is the private key, n is the modulus (shared between the private and public key).

Then it can be verified by this math:

 m = s^e % n

Where e is the public key.

Of course the keys must be generated to a specific mathematical standard for this to work. And sometimes the keys get to enormous sizes. Again, all of this is done via integers, so you would have to convert the text into decimal and back.

For more information, and more math, check out this page.

EDIT: I thought I should mention why you would want to use public key cryptography. Basically, it protects against two things: the message is verifiable and cannot be faked.