RSA Encryption process in PHP

In an effort to understand the asymmetric encryption process I outlined a simple PHP script to encrypt and decrypt simple numbers. I noticed that after a while given numbers to encrypt/decrypt the algorithm would fail, as in the decrypted and initial numbers didn't match. I put a loop in to see how the algorithm would perform when ecrypting and decrypting 100 numbers and after the number 32 the process fell apart.

Is this because p*q = 33?

<?php

# Test encrypto algo

// Choose prime keys
$p = 47; $q = 71; 
// Compute n = pq
$n = $p*$q;
// Choose e such that 1 < e < f(n) and e and n are coprime
$e = 79;
// Compute a value for d such that (d * e) % f(n) = 1
$d = 1019;
// Compute f(n) = (p-1)(q-1)
$z = ($p - 1)*($q - 1);
// Create public and private keys
$pubK = array('n' => $n, 'e' => $e);
$privK = array('n'=> $n, 'd' => $d);
// Boundary for loop
$l = 100;

// Perform encypt/decrypt on 1..100
for($i = 1; $i <= $l; $i++)
{
    $enc = enc($i, $pubK);
    $dec = dec($enc, $privK);
    print "encrypted <b>$i</b> = $enc decrypted $enc = <b>$dec</b> ";
    if($i == $dec)
        print "Success<br>";
    else
        print "Fail<br>";
}

// Encrypt sample with public key
function enc($sample, $key)
{
    return bcmod(bcpow($sample,$key['e']),$key['n']);
}
// Decrypt encrypted sample with private key
function dec($sample, $key)
{
    return bcmod(bcpow($sample, $key['d']),$key['n']);
}

?>

Answers


http://en.wikipedia.org/wiki/RSA_(algorithm)

2.2 Encryption:

[...] Bob then wishes to send message M to Alice. He first turns M into an integer m, such that 0 ≤ m < n by using an agreed-upon reversible protocol known as a padding scheme. ...Alice transmits her public key (n, e) to Bob and keeps the

This does not hold here, therefore you need to use larger factorizations.


The problem is in small $p and $q values. As we noticed in comments, bigger value of $n=$p*$q starts returning fails later.

Problems start when $i>$n, then encription/decription returns wrong numbers.

What to do? In real problems, $p and $q are huge numbers. Also message is splited into smaller one and provides as stream of many values. For example you can decrypt parts of your number, and then sum it to get final value. In more advanced cases, code every symbol as a number, and encode/decode they one by one.


Need Your Help

How can an executable .jar file be run without the command prompt?

java jar

I have a very basic .jar file that successfully runs, though I can only seem to run it by doing one of two things:

Pass OS values to extJS app

apache extjs external

How can I access external system values from within an ExtJS application? One of the main reasons I need to do this is that instead of doing authentication from my ExtJS application, I am using Apa...

About UNIX Resources Network

Original, collect and organize Developers related documents, information and materials, contains jQuery, Html, CSS, MySQL, .NET, ASP.NET, SQL, objective-c, iPhone, Ruby on Rails, C, SQL Server, Ruby, Arrays, Regex, ASP.NET MVC, WPF, XML, Ajax, DataBase, and so on.