rsa_source/rsa/pkcs1.py

   1 # -*- coding: utf-8 -*-
   2 #
   3 #  Copyright 2011 Sybren A. Stüvel <sybren@stuvel.eu>
   4 #
   5 #  Licensed under the Apache License, Version 2.0 (the "License");
   6 #  you may not use this file except in compliance with the License.
   7 #  You may obtain a copy of the License at
   8 #
   9 #      http://www.apache.org/licenses/LICENSE-2.0
  10 #
  11 #  Unless required by applicable law or agreed to in writing, software
  12 #  distributed under the License is distributed on an "AS IS" BASIS,
  13 #  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14 #  See the License for the specific language governing permissions and
  15 #  limitations under the License.
  16
  17 '''Functions for PKCS#1 version 1.5 encryption and signing
  18
  19 This module implements certain functionality from PKCS#1 version 1.5. For a
  20 very clear example, read http://www.di-mgt.com.au/rsa_alg.html#pkcs1schemes
  21
  22 At least 8 bytes of random padding is used when encrypting a message. This makes
  23 these methods much more secure than the ones in the ``rsa`` module.
  24
  25 WARNING: this module leaks information when decryption or verification fails.
  26 The exceptions that are raised contain the Python traceback information, which
  27 can be used to deduce where in the process the failure occurred. DO NOT PASS
  28 SUCH INFORMATION to your users.
  29 '''
  30
  31 import hashlib
  32 import os
  33
  34 from rsa import common, transform, core, varblock
  35
  36 # ASN.1 codes that describe the hash algorithm used.
  37 HASH_ASN1 = {
  38     'MD5': '\x30\x20\x30\x0c\x06\x08\x2a\x86\x48\x86\xf7\x0d\x02\x05\x05\x00\x04\x10',
  39     'SHA-1': '\x30\x21\x30\x09\x06\x05\x2b\x0e\x03\x02\x1a\x05\x00\x04\x14',
  40     'SHA-256': '\x30\x31\x30\x0d\x06\x09\x60\x86\x48\x01\x65\x03\x04\x02\x01\x05\x00\x04\x20',
  41     'SHA-384': '\x30\x41\x30\x0d\x06\x09\x60\x86\x48\x01\x65\x03\x04\x02\x02\x05\x00\x04\x30',
  42     'SHA-512': '\x30\x51\x30\x0d\x06\x09\x60\x86\x48\x01\x65\x03\x04\x02\x03\x05\x00\x04\x40',
  43 }
  44
  45 HASH_METHODS = {
  46     'MD5': hashlib.md5,
  47     'SHA-1': hashlib.sha1,
  48     'SHA-256': hashlib.sha256,
  49     'SHA-384': hashlib.sha384,
  50     'SHA-512': hashlib.sha512,
  51 }
  52
  53 class CryptoError(Exception):
  54     '''Base class for all exceptions in this module.'''
  55
  56 class DecryptionError(CryptoError):
  57     '''Raised when decryption fails.'''
  58
  59 class VerificationError(CryptoError):
  60     '''Raised when verification fails.'''
  61
  62 def _pad_for_encryption(message, target_length):
  63     r'''Pads the message for encryption, returning the padded message.
  64
  65     :return: 00 02 RANDOM_DATA 00 MESSAGE
  66
  67     >>> block = _pad_for_encryption('hello', 16)
  68     >>> len(block)
  69     16
  70     >>> block[0:2]
  71     '\x00\x02'
  72     >>> block[-6:]
  73     '\x00hello'
  74
  75     '''
  76
  77     max_msglength = target_length - 11
  78     msglength = len(message)
  79
  80     if msglength > max_msglength:
  81         raise OverflowError('%i bytes needed for message, but there is only'
  82             ' space for %i' % (msglength, max_msglength))
  83
  84     # Get random padding
  85     padding = ''
  86     padding_length = target_length - msglength - 3
  87
  88     # We remove 0-bytes, so we'll end up with less padding than we've asked for,
  89     # so keep adding data until we're at the correct length.
  90     while len(padding) < padding_length:
  91         needed_bytes = padding_length - len(padding)
  92
  93         # Always read at least 8 bytes more than we need, and trim off the rest
  94         # after removing the 0-bytes. This increases the chance of getting
  95         # enough bytes, especially when needed_bytes is small
  96         new_padding = os.urandom(needed_bytes + 5)
  97         new_padding = new_padding.replace('\x00', '')
  98         padding = padding + new_padding[:needed_bytes]
  99
 100     assert len(padding) == padding_length
 101
 102     return ''.join(['\x00\x02',
 103                     padding,
 104                     '\x00',
 105                     message])
 106
 107
 108 def _pad_for_signing(message, target_length):
 109     r'''Pads the message for signing, returning the padded message.
 110
 111     The padding is always a repetition of FF bytes.
 112
 113     :return: 00 01 PADDING 00 MESSAGE
 114
 115     >>> block = _pad_for_signing('hello', 16)
 116     >>> len(block)
 117     16
 118     >>> block[0:2]
 119     '\x00\x01'
 120     >>> block[-6:]
 121     '\x00hello'
 122     >>> block[2:-6]
 123     '\xff\xff\xff\xff\xff\xff\xff\xff'
 124
 125     '''
 126
 127     max_msglength = target_length - 11
 128     msglength = len(message)
 129
 130     if msglength > max_msglength:
 131         raise OverflowError('%i bytes needed for message, but there is only'
 132             ' space for %i' % (msglength, max_msglength))
 133
 134     padding_length = target_length - msglength - 3
 135
 136     return ''.join(['\x00\x01',
 137                     padding_length * '\xff',
 138                     '\x00',
 139                     message])
 140
 141
 142 def encrypt(message, pub_key):
 143     '''Encrypts the given message using PKCS#1 v1.5
 144
 145     :param message: the message to encrypt. Must be a byte string no longer than
 146         ``k-11`` bytes, where ``k`` is the number of bytes needed to encode
 147         the ``n`` component of the public key.
 148     :param pub_key: the :py:class:`rsa.PublicKey` to encrypt with.
 149     :raise OverflowError: when the message is too large to fit in the padded
 150         block.
 151
 152     >>> from rsa import key, common
 153     >>> (pub_key, priv_key) = key.newkeys(256)
 154     >>> message = 'hello'
 155     >>> crypto = encrypt(message, pub_key)
 156
 157     The crypto text should be just as long as the public key 'n' component:
 158
 159     >>> len(crypto) == common.byte_size(pub_key.n)
 160     True
 161
 162     '''
 163
 164     keylength = common.byte_size(pub_key.n)
 165     padded = _pad_for_encryption(message, keylength)
 166
 167     payload = transform.bytes2int(padded)
 168     encrypted = core.encrypt_int(payload, pub_key.e, pub_key.n)
 169     block = transform.int2bytes(encrypted, keylength)
 170
 171     return block
 172
 173 def decrypt(crypto, priv_key):
 174     r'''Decrypts the given message using PKCS#1 v1.5
 175
 176     The decryption is considered 'failed' when the resulting cleartext doesn't
 177     start with the bytes 00 02, or when the 00 byte between the padding and
 178     the message cannot be found.
 179
 180     :param crypto: the crypto text as returned by :py:func:`rsa.encrypt`
 181     :param priv_key: the :py:class:`rsa.PrivateKey` to decrypt with.
 182     :raise DecryptionError: when the decryption fails. No details are given as
 183         to why the code thinks the decryption fails, as this would leak
 184         information about the private key.
 185
 186
 187     >>> import rsa
 188     >>> (pub_key, priv_key) = rsa.newkeys(256)
 189
 190     It works with strings:
 191
 192     >>> crypto = encrypt('hello', pub_key)
 193     >>> decrypt(crypto, priv_key)
 194     'hello'
 195
 196     And with binary data:
 197
 198     >>> crypto = encrypt('\x00\x00\x00\x00\x01', pub_key)
 199     >>> decrypt(crypto, priv_key)
 200     '\x00\x00\x00\x00\x01'
 201
 202     Altering the encrypted information will *likely* cause a
 203     :py:class:`rsa.pkcs1.DecryptionError`. If you want to be *sure*, use
 204     :py:func:`rsa.sign`.
 205
 206
 207     .. warning::
 208
 209         Never display the stack trace of a
 210         :py:class:`rsa.pkcs1.DecryptionError` exception. It shows where in the
 211         code the exception occurred, and thus leaks information about the key.
 212         It's only a tiny bit of information, but every bit makes cracking the
 213         keys easier.
 214
 215     >>> crypto = encrypt('hello', pub_key)
 216     >>> crypto = 'X' + crypto[1:] # change the first byte
 217     >>> decrypt(crypto, priv_key)
 218     Traceback (most recent call last):
 219     ...
 220     DecryptionError: Decryption failed
 221
 222     '''
 223
 224     blocksize = common.byte_size(priv_key.n)
 225     encrypted = transform.bytes2int(crypto)
 226     decrypted = core.decrypt_int(encrypted, priv_key.d, priv_key.n)
 227     cleartext = transform.int2bytes(decrypted, blocksize)
 228
 229     # If we can't find the cleartext marker, decryption failed.
 230     if cleartext[0:2] != '\x00\x02':
 231         raise DecryptionError('Decryption failed')
 232
 233     # Find the 00 separator between the padding and the message
 234     try:
 235         sep_idx = cleartext.index('\x00', 2)
 236     except ValueError:
 237         raise DecryptionError('Decryption failed')
 238
 239     return cleartext[sep_idx+1:]
 240
 241 def sign(message, priv_key, hash):
 242     '''Signs the message with the private key.
 243
 244     Hashes the message, then signs the hash with the given key. This is known
 245     as a "detached signature", because the message itself isn't altered.
 246
 247     :param message: the message to sign. Can be an 8-bit string or a file-like
 248         object. If ``message`` has a ``read()`` method, it is assumed to be a
 249         file-like object.
 250     :param priv_key: the :py:class:`rsa.PrivateKey` to sign with
 251     :param hash: the hash method used on the message. Use 'MD5', 'SHA-1',
 252         'SHA-256', 'SHA-384' or 'SHA-512'.
 253     :return: a message signature block.
 254     :raise OverflowError: if the private key is too small to contain the
 255         requested hash.
 256
 257     '''
 258
 259     # Get the ASN1 code for this hash method
 260     if hash not in HASH_ASN1:
 261         raise ValueError('Invalid hash method: %s' % hash)
 262     asn1code = HASH_ASN1[hash]
 263
 264     # Calculate the hash
 265     hash = _hash(message, hash)
 266
 267     # Encrypt the hash with the private key
 268     cleartext = asn1code + hash
 269     keylength = common.byte_size(priv_key.n)
 270     padded = _pad_for_signing(cleartext, keylength)
 271
 272     payload = transform.bytes2int(padded)
 273     encrypted = core.encrypt_int(payload, priv_key.d, priv_key.n)
 274     block = transform.int2bytes(encrypted, keylength)
 275
 276     return block
 277
 278 def verify(message, signature, pub_key):
 279     '''Verifies that the signature matches the message.
 280
 281     The hash method is detected automatically from the signature.
 282
 283     :param message: the signed message. Can be an 8-bit string or a file-like
 284         object. If ``message`` has a ``read()`` method, it is assumed to be a
 285         file-like object.
 286     :param signature: the signature block, as created with :py:func:`rsa.sign`.
 287     :param pub_key: the :py:class:`rsa.PublicKey` of the person signing the message.
 288     :raise VerificationError: when the signature doesn't match the message.
 289
 290     .. warning::
 291
 292         Never display the stack trace of a
 293         :py:class:`rsa.pkcs1.VerificationError` exception. It shows where in
 294         the code the exception occurred, and thus leaks information about the
 295         key. It's only a tiny bit of information, but every bit makes cracking
 296         the keys easier.
 297
 298     '''
 299
 300     blocksize = common.byte_size(pub_key.n)
 301     encrypted = transform.bytes2int(signature)
 302     decrypted = core.decrypt_int(encrypted, pub_key.e, pub_key.n)
 303     clearsig = transform.int2bytes(decrypted, blocksize)
 304
 305     # If we can't find the signature  marker, verification failed.
 306     if clearsig[0:2] != '\x00\x01':
 307         raise VerificationError('Verification failed')
 308
 309     # Find the 00 separator between the padding and the payload
 310     try:
 311         sep_idx = clearsig.index('\x00', 2)
 312     except ValueError:
 313         raise VerificationError('Verification failed')
 314
 315     # Get the hash and the hash method
 316     (method_name, signature_hash) = _find_method_hash(clearsig[sep_idx+1:])
 317     message_hash = _hash(message, method_name)
 318
 319     # Compare the real hash to the hash in the signature
 320     if message_hash != signature_hash:
 321         raise VerificationError('Verification failed')
 322
 323 def _hash(message, method_name):
 324     '''Returns the message digest.
 325
 326     :param message: the signed message. Can be an 8-bit string or a file-like
 327         object. If ``message`` has a ``read()`` method, it is assumed to be a
 328         file-like object.
 329     :param method_name: the hash method, must be a key of
 330         :py:const:`HASH_METHODS`.
 331
 332     '''
 333
 334     if method_name not in HASH_METHODS:
 335         raise ValueError('Invalid hash method: %s' % method_name)
 336
 337     method = HASH_METHODS[method_name]
 338     hasher = method()
 339
 340     if hasattr(message, 'read') and hasattr(message.read, '__call__'):
 341         # read as 1K blocks
 342         for block in varblock.yield_fixedblocks(message, 1024):
 343             hasher.update(block)
 344     else:
 345         # hash the message object itself.
 346         hasher.update(message)
 347
 348     return hasher.digest()
 349
 350
 351 def _find_method_hash(method_hash):
 352     '''Finds the hash method and the hash itself.
 353
 354     :param method_hash: ASN1 code for the hash method concatenated with the
 355         hash itself.
 356
 357     :return: tuple (method, hash) where ``method`` is the used hash method, and
 358         ``hash`` is the hash itself.
 359
 360     :raise VerificationFailed: when the hash method cannot be found
 361
 362     '''
 363
 364     for (hashname, asn1code) in HASH_ASN1.iteritems():
 365         if not method_hash.startswith(asn1code):
 366             continue
 367
 368         return (hashname, method_hash[len(asn1code):])
 369
 370     raise VerificationError('Verification failed')
 371
 372
 373 __all__ = ['encrypt', 'decrypt', 'sign', 'verify',
 374            'DecryptionError', 'VerificationError', 'CryptoError']
 375
 376 if __name__ == '__main__':
 377     print 'Running doctests 1000x or until failure'
 378     import doctest
 379
 380     for count in range(1000):
 381         (failures, tests) = doctest.testmod()
 382         if failures:
 383             break
 384
 385         if count and count % 100 == 0:
 386             print '%i times' % count
 387
 388     print 'Doctests done'