RSA decryption with manual modulus and exponent

Get help with using the PHP Secure Communications Library.

Moderator: Nuxius

Forum rules
The purpose of this forum is to provide support for phpseclib, a pure PHP SSH / SFTP / RSA library.

Posts by new users are held in a moderation queue and are not publicly visible until the post is approved.

RSA decryption with manual modulus and exponent

Postby philip_o » Fri Mar 23, 2012 11:22 pm

Hello all,

I'm trying to implement a routine in order to use the following data verification mechanism:

    - A GET parameter is received (Base16) that needs to be converted to a binary string;
    - This binary string needs to be decrypted with a RSA key from a binary file that has been received earlier;
    - The resulting SHA hash will be used to verify the complete call.
At this moment I'm stuck in the process, although I was able to retrieve a valid looking key.

The binary file for the RSA key, has the following structure:

    - The first 4 bytes (in bigEndian) contain the RSA key size in bits.
    - The next byte contains a 1 or 0 value, to indicate transmission in bigEndian (1) or littleEndian (0).
    - The next byte sequence (the number of bytes is specified by the key size) reflects the RSA key modulus in bigEndian
    - The final byte sequence (the number of bytes is also specified by the key size) reflects the RSA key exponent in bigEndian
I'm reading this key with the following code, where strrev is used to read the bigEndian values:

Code: Select all
function binToInt($input)
{   
    $len = strlen($input);
    $result = 0;
    for ($i=0; $i < $len; $i++) {
        $result += ord($input[$i]) << (($len-$i-1)*8);
    }
    return $result;
}
$keyContent = file_get_contents('keyfile.bin');
$size = binToInt(strrev(substr($keyContent, 0, 4))) / 8;
$bigEndian = binToInt(strrev(substr($keyContent, 4, 1)));
$modulus = strrev(substr($keyContent, 5, $size));
$exponent = strrev(substr($keyContent, 5 + $size, $size));

With these values I create the RSA as follows, based on the only example that I found that actually resulted in a valid key:

Code: Select all
$rsa = new Crypt_RSA();
$rsa->modulus = new Math_BigInteger(($modulus), 256);
$rsa->exponent = new Math_BigInteger(($exponent), 256);
$rsa->publicExponent = new Math_BigInteger(($exponent), 256);
$rsa->k = strlen($rsa->modulus->toBytes());

If at this moment I export the public key (as a check), I do get output that seems to present a valid key:

-----BEGIN PUBLIC KEY-----
MIIBCAKBgQDTZjlab/zwVMqfbuLba4kyc/STDKlKIS+O8iXeHm4cWodjLF2RSLzmFY9XqT/Apleg
[ ... ]
+tfQIRcT9QuIaSyHxfluo9N4bzMvQl/C6pgDRq+UDN3t4DrnxlAUPw==
-----END PUBLIC KEY-----

Finally the query string parameter is being read like:

Code: Select all
/*
 * hex2bin
 * Convert a hex-string to binary-string (the way back from bin2hex)
 * (a found function that seems to do the trick)
 */
function hex2bin($h)
{
    if (!is_string($h)) return null;
    $r='';
    for ($a=0; $a<strlen($h); $a+=2) {
        $r .= chr(hexdec($h{$a}.$h{($a+1)}));
    }
    return $r;
}
$encrypted = hex2bin($_GET['encryptedHash']);
// Neither is working:
// $encrypted = hex2bin(strrev($_GET['encryptedHash']));

However, when I'm trying the most crucial step, the decryption fails no matter what I try:

Code: Select all
$rsa->decrypt($encrypted);
$rsa->decrypt(strrev($encrypted));

It always returns FALSE and a notice (Decryption error in phpseclib0.2.2/Crypt/RSA.php on line 1819).
Just as a reference, the failing check on line 1818 is: if ($lHash != $lHash2) {

I'm working at this moment on OSX 10.6.8 but the code should be able to work on Debian (just in case this matters for the bigEndian vs. littleEndian)

It's getting very frustrating, especially as I (perhaps very misplaced) think I'm very close...

Any help or suggestion is more than welcome.

Thanks in advance

Philip
Last edited by philip_o on Sun Mar 25, 2012 6:48 am, edited 1 time in total.
philip_o
Traveler
 
Posts: 4
Joined: Wed Mar 14, 2012 12:08 pm

Re: RSA decryption withHello all, I manual modulus and expo

Postby TerraFrost » Sun Mar 25, 2012 2:06 am

Could you post the public key in its original format along with a sample encrypted message?
TerraFrost
Legendary Guard
 
Posts: 12357
Joined: Wed Dec 04, 2002 6:37 am

Re: RSA decryption withHello all, I manual modulus and expo

Postby TerraFrost » Sun Mar 25, 2012 3:09 am

BTW, PHP is big endian by default. strrev() is probably not something you want to be doing. ie.

"\1\0\0\0". According to your program that'd be a 1. According to what the specs you've posted, however, it seems like it should be 16,777,216.

Personally, I think a more straight forward parsing would be to do this:

Code: Select all
list(, $size) = unpack('N', substr($keyContent, 0, 4));
$size/= 8;
$bigEndian = ord($keyContent[4]);
$modulus = substr($keyContent, 5, $size);
$exponent = substr($keyContent, $size + 5);
TerraFrost
Legendary Guard
 
Posts: 12357
Joined: Wed Dec 04, 2002 6:37 am

Re: RSA decryption with manual modulus and exponent

Postby philip_o » Sun Mar 25, 2012 7:05 am

Thanks for the suggestion. If I adjust the reading of the key with the code of your example, I still get a public key value with:

Code: Select all
$key = $rsa->getPublicKey(CRYPT_RSA_PRIVATE_FORMAT_PKCS1);

But this time it doesn't look base64, which I had expected:

Code: Select all
-----BEGIN PUBLIC KEY-----
MIIBBwKCAQEA63noRahzGKCGFUEL3VytxDH9aVANoDxBNLJ9eur0edFT7+Ec7khmM7VwHaUquk6n
ShT8giD+F/7e7Ep0m8rrwbD+RK70kDDYbD1p1juHlKBXpsA/qVePFea8SJFdLGOHWhxuHt4l8o4v
IUqpDJP0czKJa9vibp/KVPD8b1o5ZtM/FFDG5zrg7d0MlK9GA5jqwl9CLzNveNOjbvnFhyxpiAv1
Exch0Nf6kB8GiM6lAeWiUDuCYqgeuajXQarPVFdcTzqN2N9oQDAZfQL57dbbqOt6nMRF57qHWvxc
wagAhqc5JlfpAG+KCIi2Xbr7GInJTwoiVr0P31YLVaXO1Dq3owIA
-----END PUBLIC KEY-----

The base64 I received with strrev, which was why I added it. Also, I know the argument is a bit weak, but with it, I receive a key size of 128 and bigEndian indicator of 1, which both fit to the actual key. Without it, as you indicate, I would get values that were too large.

Unfortunately, also this new route leads to the same Decryption failed.

An example base16 string that I'd get in the QUERY STRING would be:

Code: Select all
encrypted=433377130DAE99F8ED703209EC9AC7AFA867A83083984D85EBFDD2B1CF69ABA6E15DED57BFF4F5E1453D15268C80A161F19F876BC896400ABE446456812A125463AF097BCAC0A81FB450D407DB24369B21D88EDCC4EC1D110A6BBF8B69B3C81A80853EF0DE0AF1CDE60381B4EA2F19F67C9E12C836969E9D01C7193AEB88E8A3
Last edited by philip_o on Tue Mar 27, 2012 4:41 pm, edited 1 time in total.
philip_o
Traveler
 
Posts: 4
Joined: Wed Mar 14, 2012 12:08 pm

Re: RSA decryption with manual modulus and exponent

Postby TerraFrost » Sun Mar 25, 2012 4:04 pm

What was the plaintext corresponding to the ciphertext you posted?

Also, if you could post the code you used to generate that ciphertext that'd be helpful.

Thanks!
TerraFrost
Legendary Guard
 
Posts: 12357
Joined: Wed Dec 04, 2002 6:37 am

Re: RSA decryption with manual modulus and exponent

Postby philip_o » Sun Mar 25, 2012 4:22 pm

First of all, thank you for your time!

The plaintext version of the ciphertext should be a SHA-1 hash of the QUERY STRING, followed by some information (for example, generation time and version number) of the call, but for this specific cypher I do not have the plaintext available. The resulting SHA-1 hash is the most important part, as it will be used to verify the received data.

Unfortunately I do not have access to the system that generates the cypher (as it's an external system). However tomorrow I will have access to sample C++ code that should be able to generate a similar ciphertext, as we will need to use this to encrypt the information we're sending back to the system. I hoped that this encryption route would be an easy follow-up, as soon as the decryption was successful.
philip_o
Traveler
 
Posts: 4
Joined: Wed Mar 14, 2012 12:08 pm

Re: RSA decryption with manual modulus and exponent

Postby TerraFrost » Sun Mar 25, 2012 9:05 pm

It sounds like signatures would be more appropriate for what you're trying to do. eg. instead of doing $rsa->decrypt($ciphertext) == $hash you should be doing $rsa->verify($plaintext, $signature).

Maybe the server you're trying to connect to actually is encrypting the hash instead of signing it (per the PKCS1 standards they're not the same) but in lieu of having seen the specs, it's also possible that you're just misinterpreting it. It's also possible that the documentation is just poorly written and it should say one thing when it instead says something else.

Having the plaintext should help me figure it out.
TerraFrost
Legendary Guard
 
Posts: 12357
Joined: Wed Dec 04, 2002 6:37 am

Re: RSA decryption with manual modulus and exponent

Postby philip_o » Sun Mar 25, 2012 9:49 pm

Based on the indeed poor documentation, I'd say signatures do not apply here.
If I understand it correct, to use signatures you must know the exact plaintext in advance, which I cannot.

Perhaps the only available documentation for the encryption process (so the opposite of above example) would confirm this:

It reads:
    1. Create a SHA-1 hash of the transaction data, i.e. the query string.
    2. Concatenate to this hash descriptive information of the enity that generate it, along with the date and time. (This step makes me think that signatures wouldn't not work)
    3. Encrypt the result using the RSA private key.
    4. Add the cipher text in base16 format to the query string.
This would imply that the validation check on "the other" side would only consist in checking the first part of the decrypted text (thus ignoring the descriptive information):

Code: Select all
$localSha1Hash == substr($decrypted, 0, strlen($localSha1Hash));

If you would be willing to have a look, I can send you the sample C++ code for both the encryption and decryption per PM. I can then also include a complete query string of the cipher-text of the previous message, but I don't know which descriptive information has been added to the inner SHA-1 hash. In fact, by starting with the decryption I was hoping to get more insight in the kind of descriptive information I had to include during encryption, as it's no clearly stated in documentation.
philip_o
Traveler
 
Posts: 4
Joined: Wed Mar 14, 2012 12:08 pm

Re: RSA decryption with manual modulus and exponent

Postby TerraFrost » Mon Mar 26, 2012 1:31 am

Yeah... let's do that. Send me the info.

Fwiw, I tried to do raw decryption - instead of OAEP or PKCS#1 padded decryption - and that didn't work either:

Code: Select all
$c = new Math_BigInteger(pack('H*', '433377130DAE99F8ED703209EC9AC7AFA867A83083984D85EBFDD2B1CF69ABA6E15DED57BFF4F5E1453D15268C80A161F19F876BC896400ABE446456812A125463AF097BCAC0A81FB450D407DB24369B21D88EDCC4EC1D110A6BBF8B69B3C81A80853EF0DE0AF1CDE60381B4EA2F19F67C9E12C836969E9D01C7193AEB88E8A3'), 256);
echo $rsa->_exponentiate($c)->toBytes();

Well, who knows... maybe it did. OAEP / PKCS#1 padding guarantee that if it's been decrypted that it's been decrypted correctly and that what you get is of the length that it should be. Raw RSA decryption doesn't do any of that. Maybe the above does decrypt it correctly and maybe the date / time are encoded as raw bytes instead of printable strings or something.
TerraFrost
Legendary Guard
 
Posts: 12357
Joined: Wed Dec 04, 2002 6:37 am

Re: RSA decryption with manual modulus and exponent

Postby jesusangel » Thu Aug 29, 2013 11:27 am

Hi!
I'm facing the same problem as the user who started this thread.

Would you be so kind to tell me if you solved this issue?

I'm stuck decrypting / verifing the MAC signature.

While decrypting the MAC code I get:

With default EncryptionMode:
Code: Select all
PHP Notice:  Decryption error in /home/..../phpseclib/Crypt/RSA.php on line 2120
PHP Stack trace:
PHP   1. {main}() /home/..../test.php:0
PHP   2. Crypt_RSA->decrypt($ciphertext = 'O\026\025\032/<$�:��L#\037�`�l\032��GG_�+ԁX�k\030\023"d1f��e�NE��&�T@��\024fM;C�*\004Ӫ��\0175u@\035/b����蕩�{��e�*\016�\b$\025QuG@�92W��#N г�~�8Ec�\023\027ūWb]�=0�yI\035��') /home/..../test.php:59
PHP   3. Crypt_RSA->_rsaes_oaep_decrypt($c = 'O\026\025\032/<$�:��L#\037�`�l\032��GG_�+ԁX�k\030\023"d1f��e�NE��&�T@��\024fM;C�*\004Ӫ��\0175u@\035/b����蕩�{��e�*\016�\b$\025QuG@�92W��#N г�~�8Ec�\023\027ūWb]�=0�yI\035��', $l = *uninitialized*) /home/..../phpseclib/Crypt/RSA.php:2637
PHP   4. user_error('Decryption error') /home/....phpseclib/Crypt/RSA.php:2120


With CRYPT_RSA_ENCRYPTION_PKCS1 EncryptionMode:
Code: Select all
PHP Notice:  Decryption error in /home/..../phpseclib/Crypt/RSA.php on line 2225
PHP Stack trace:
PHP   1. {main}() /home/..../test.php:0
PHP   2. Crypt_RSA->decrypt($ciphertext = 'O\026\025\032/<$�:��L#\037�`�l\032��GG_�+ԁX�k\030\023"d1f��e�NE��&�T@��\024fM;C�*\004Ӫ��\0175u@\035/b����蕩�{��e�*\016�\b$\025QuG@�92W��#N г�~�8Ec�\023\027ūWb]�=0�yI\035��') /home/..../test.php:64
PHP   3. Crypt_RSA->_rsaes_pkcs1_v1_5_decrypt($c = 'O\026\025\032/<$�:��L#\037�`�l\032��GG_�+ԁX�k\030\023"d1f��e�NE��&�T@��\024fM;C�*\004Ӫ��\0175u@\035/b����蕩�{��e�*\016�\b$\025QuG@�92W��#N г�~�8Ec�\023\027ūWb]�=0�yI\035��') /home/..../phpseclib/Crypt/RSA.php:2637
PHP   4. user_error('Decryption error') /home/..../ppimac/phpseclib/Crypt/RSA.php:2225


The verification returns '0' in both cases:

Code: Select all
$rsa->verify($plaintext, hex2bin($mac_str)));


Kind regards.
jesusangel
Traveler
 
Posts: 3
Joined: Thu Aug 29, 2013 11:17 am

Re: RSA decryption with manual modulus and exponent

Postby jesusangel » Thu Aug 29, 2013 11:57 am

Test case:

Binary key attached in s4bppi.txt.

Base 64 encoded modulus and exponent are:

Modulus
Code: Select all
02Y5Wm/88FTKn27i22uJMnP0kwypSiEvjvIl3h5uHFqHYyxdkUi85hWPV6k/wKZXoJSHO9ZpPWzYMJD0rkT+sMHrypt0Suze/hf+IIL8FEqnTroqpR1wtTNmSO4c4e9T0Xn06np9sjRBPKANUGn9McStXN0LQRWGoBhzqEXoees=


Exponent
Code: Select all
o7c61M6lVQtW3w+9ViIKT8mJGPu6XbaICIpvAOlXJjmnhgCowVz8Woe650XEnHrrqNvW7fkCfRkwQGjf2I06T1xXVM+qQdeouR6oYoI7UKLlAaXOiAYfkPrX0CEXE/ULiGksh8X5bqPTeG8zL0JfwuqYA0avlAzd7eA658ZQFD8=


Public key in PEM format is:
Code: Select all
-----BEGIN PUBLIC KEY-----
MIIBIDANBgkqhkiG9w0BAQEFAAOCAQ0AMIIBCAKBgQDTZjlab/zwVMqfbuLba4ky
c/STDKlKIS+O8iXeHm4cWodjLF2RSLzmFY9XqT/ApleglIc71mk9bNgwkPSuRP6w
wevKm3RK7N7+F/4ggvwUSqdOuiqlHXC1M2ZI7hzh71PRefTqen2yNEE8oA1Qaf0x
xK1c3QtBFYagGHOoReh56wKBgQCjtzrUzqVVC1bfD71WIgpPyYkY+7pdtogIim8A
6VcmOaeGAKjBXPxah7rnRcSceuuo29bt+QJ9GTBAaN/YjTpPXFdUz6pB16i5Hqhi
gjtQouUBpc6IBh+Q+tfQIRcT9QuIaSyHxfluo9N4bzMvQl/C6pgDRq+UDN3t4Drn
xlAUPw==
-----END PUBLIC KEY-----


Plain text is the result of this sentence:
Code: Select all
sha1('wc-api=WC_4B_PASAT&details=1&order=0840&store=PI00024114').'Sistema 4B: Pasarela de Pagos por Internet, Versión 5.10, Release 20228'.date('/d/m/Y h:i:j');

As you can see, the plaintex is unknown cause of it includes the generated date. I have to decrypt the cyphertext to get the hash and check it against the kown query_string.

Base 16 encoded crypted text is:
Code: Select all
4F16151A2F3C24D33AF6C94C231F8660F76C1A81AB47475F962BD48158E76B181322643166C7C365844E45D6E026BC5440F3C014664D3B43862A04D3AA8BD30F3575401D2F62AA8580DDE895A99E7B86C265E0A02A0EDC0824155175474095393257B581234E20D0B3CE7EFA384563DF1317C5AB57625DD43D30AB79491D9FF8


But I can't decrypt this string... I think it is big endian.

Remember how ciphertext is obtained:

1. Create a SHA-1 hash of the transaction data, i.e. the query string.
2. Concatenate to this hash descriptive information of the enity that generate it, along with the date and time. (This step makes me think that signatures wouldn't not work)
3. Encrypt the result using the RSA private key.
4. Add the cipher text in base16 format to the query string.

Kind regards.
Attachments
s4bppi.txt
Raw public key. Big endian. First 4 bytes set modulus and exponent size: bytesSize = floor( (value+7)/8 ). Next one byte says big endian format (value = 1) and the next ones are modulus and exponent (128 bytes) each.
(261 Bytes) Downloaded 112 times
jesusangel
Traveler
 
Posts: 3
Joined: Thu Aug 29, 2013 11:17 am

Re: RSA decryption with manual modulus and exponent

Postby jesusangel » Thu Aug 29, 2013 12:06 pm

Hi again!

This is the code I'm using:

Code: Select all
<?php

include_once 'phpseclib/Crypt/RSA.php';
include_once 'phpseclib/Math/BigInteger.php';

// Read the public signature
$keyContent = file_get_contents('s4bppi.kyp');
$size = binToInt(strrev(substr($keyContent, 0, 4))) / 8;
$bigEndian = binToInt(strrev(substr($keyContent, 4, 1)));
$modulus_bytes = strrev(substr($keyContent, 5, $size));
$exponent_bytes = strrev(substr($keyContent, 5 + $size, $size));

// Load RSA public key from modulus and exponent
$rsa = new Crypt_RSA();
$modulus = new Math_BigInteger(($modulus_bytes), 256);
$exponent = new Math_BigInteger(($exponent_bytes), 256);

$rsa->loadKey(array('n' => $modulus, 'e' => $exponent));
$rsa->setPublicKey();

// Hash algorithm is SHA1
$rsa->setHash('sha1');

//echo "\n".$rsa->getPublicKey()."\n";

// Plaintext is something like this:
$query_string = sha1('/?wc-api=WC_4B_PASAT&details=1&order=0840&store=PI00024114').'Sistema 4B: Pasarela de Pagos por Internet, Versión 5.10, Release 20228'.date('d/m/Y h:i:j');

// Received cyphertext. Base16 encoded. I think it's big endian
$mac_str = '4F16151A2F3C24D33AF6C94C231F8660F76C1A81AB47475F962BD48158E76B181322643166C7C365844E45D6E026BC5440F3C014664D3B43862A04D3AA8BD30F3575401D2F62AA8580DDE895A99E7B86C265E0A02A0EDC0824155175474095393257B581234E20D0B3CE7EFA384563DF1317C5AB57625DD43D30AB79491D9FF8';

// First try to decrypt it
$c = new Math_BigInteger(pack('H*', $mac_str), 256);
echo "Test: " . $rsa->_exponentiate($c)->toBytes() . "\n";

// Second try to decrypt it
echo $rsa->decrypt(hex2bin($mac_str));

// Third try
$rsa->setEncryptionMode(CRYPT_RSA_ENCRYPTION_PKCS1);
echo $rsa->decrypt(hex2bin($mac_str));

function binToInt($input)
{   
    $len = strlen($input);
    $result = 0;
    for ($i=0; $i < $len; $i++) {
        $result += ord($input[$i]) << (($len-$i-1)*8);
    }
    return $result;
}
jesusangel
Traveler
 
Posts: 3
Joined: Thu Aug 29, 2013 11:17 am

Re: RSA decryption with manual modulus and exponent

Postby TerraFrost » Mon Sep 02, 2013 4:30 pm

We never did. He was trying to make phpseclib interoperable with some properietary software. I suggested he contact them for more information and he tried but wasn't ever able to get ahold of them.

Anyway, looking at your code...

Code: Select all
// Plaintext is something like this:
$query_string = sha1('/?wc-api=WC_4B_PASAT&details=1&order=0840&store=PI00024114').'Sistema 4B: Pasarela de Pagos por Internet, Versión 5.10, Release 20228'.date('d/m/Y h:i:j');

So... is it that or not?

If it's "something like [that]" but not exactly that then obviously signature verification won't work.

Anyway, doing $rsa->_exponentiate($c)->toBytes() suggests that (assuming the public key is correct) that it's not using OAEP padding, PKCS1 encryption padding, the PKCS1 signature scheme or PSS.

Also, the plaintext is 129 bytes long. The key is 128 bytes (1024 bits). This means OAEP and PKCS1 encryption padding couldn't be used, anyway, because the plaintext is too long.

Can you post the code you're using to generate the ciphertext?

Thanks!
TerraFrost
Legendary Guard
 
Posts: 12357
Joined: Wed Dec 04, 2002 6:37 am


Return to phpseclib support

Who is online

Users browsing this forum: No registered users and 2 guests

cron