friends/magicsig/magicsigalg.py

   1 #!/usr/bin/python2.4
   2 #
   3 # Copyright 2009 Google Inc. All Rights Reserved.
   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 """Implementation of Magic Signatures low level operations.
  18
  19 See Magic Signatures RFC for specification.  This implements
  20 the cryptographic layer of the spec, essentially signing and
  21 verifying byte buffers using a public key algorithm.
  22 """
  23
  24 __author__ = 'jpanzer@google.com (John Panzer)'
  25
  26
  27 import base64
  28 import re
  29
  30 # PyCrypto: Note that this is not available in the
  31 # downloadable GAE SDK, must be installed separately.
  32 # See http://code.google.com/p/googleappengine/issues/detail?id=2493
  33 # for why this is most easily installed under the
  34 # project's path rather than somewhere more sane.
  35 import Crypto.PublicKey
  36 import Crypto.PublicKey.RSA
  37 from Crypto.Util import number
  38
  39 import hashlib
  40
  41
  42 # Note that PyCrypto is a very low level library and its documentation
  43 # leaves something to be desired.  As a cheat sheet, for the RSA
  44 # algorithm, here's a decoding of terminology:
  45 #     n - modulus (public)
  46 #     e - public exponent
  47 #     d - private exponent
  48 #     (n, e) - public key
  49 #     (n, d) - private key
  50 #     (p, q) - the (private) primes from which the keypair is derived.
  51
  52 # Thus a public key is a tuple (n,e) and a public/private key pair
  53 # is a tuple (n,e,d).  Often the exponent is 65537 so for convenience
  54 # we default e=65537 in this code.
  55
  56
  57 def GenSampleSignature(text):
  58   """Demo using a hard coded, test public/private keypair."""
  59   demo_keypair = ('RSA.mVgY8RN6URBTstndvmUUPb4UZTdwvwmddSKE5z_jvKUEK6yk1'
  60                   'u3rrC9yN8k6FilGj9K0eeUPe2hf4Pj-5CmHww=='
  61                   '.AQAB'
  62                   '.Lgy_yL3hsLBngkFdDw1Jy9TmSRMiH6yihYetQ8jy-jZXdsZXd8V5'
  63                   'ub3kuBHHk4M39i3TduIkcrjcsiWQb77D8Q==')
  64
  65   signer = SignatureAlgRsaSha256(demo_keypair)
  66   return signer.Sign(text)
  67
  68
  69 # Utilities
  70 def _NumToB64(num):
  71   """Turns a bignum into a urlsafe base64 encoded string."""
  72   return base64.urlsafe_b64encode(number.long_to_bytes(num))
  73
  74
  75 def _B64ToNum(b64):
  76   """Turns a urlsafe base64 encoded string into a bignum."""
  77   print(b64)
  78   return number.bytes_to_long(base64.urlsafe_b64decode(b64))
  79
  80 # Patterns for parsing serialized keys
  81 _WHITESPACE_RE = re.compile(r'\s+')
  82 _KEY_RE = re.compile(
  83     r"""RSA\.
  84       (?P<mod>[^\.]+)
  85       \.
  86       (?P<exp>[^\.]+)
  87       (?:\.
  88         (?P<private_exp>[^\.]+)
  89       )?""",
  90     re.VERBOSE)
  91
  92
  93 # Implementation of the Magic Envelope signature algorithm
  94 class SignatureAlgRsaSha256(object):
  95   """Signature algorithm for RSA-SHA256 Magic Envelope."""
  96
  97   def __init__(self, rsa_key):
  98     """Initializes algorithm with key information.
  99
 100     Args:
 101       rsa_key: Key in either string form or a tuple in the
 102                format expected by Crypto.PublicKey.RSA.
 103     Raises:
 104       ValueError: The input format was incorrect.
 105     """
 106     if isinstance(rsa_key, tuple):
 107       self.keypair = Crypto.PublicKey.RSA.construct(rsa_key)
 108     else:
 109       self._InitFromString(rsa_key)
 110
 111   def ToString(self, full_key_pair=True):
 112     """Serializes key to a safe string storage format.
 113
 114     Args:
 115       full_key_pair: Whether to save the private key portion as well.
 116     Returns:
 117       The string representation of the key in the format:
 118
 119         RSA.mod.exp[.optional_private_exp]
 120
 121       Each component is a urlsafe-base64 encoded representation of
 122       the corresponding RSA key field.
 123     """
 124     mod = _NumToB64(self.keypair.n)
 125     exp = '.' + _NumToB64(self.keypair.e)
 126     private_exp = ''
 127     if full_key_pair and self.keypair.d:
 128       private_exp = '.' + _NumToB64(self.keypair.d)
 129     return 'RSA.' + mod + exp + private_exp
 130
 131   def _InitFromString(self, text):
 132     """Parses key from a standard string storage format.
 133
 134     Args:
 135       text: The key in text form.  See ToString for description
 136         of expected format.
 137     Raises:
 138       ValueError: The input format was incorrect.
 139     """
 140     # First, remove all whitespace:
 141     text = re.sub(_WHITESPACE_RE, '', text)
 142     #throw away first item and convert from base64 to long
 143     items = [_B64ToNum(item) for item in text.split('.')[1:]]
 144     self.keypair = Crypto.PublicKey.RSA.construct(items)
 145
 146   def GetName(self):
 147     """Returns string identifier for algorithm used."""
 148     return 'RSA-SHA256'
 149
 150   def _MakeEmsaMessageSha256(self, msg, modulus_size, logf=None):
 151     """Algorithm EMSA_PKCS1-v1_5 from PKCS 1 version 2.
 152
 153     This is derived from keyczar code, and implements the
 154     additional ASN.1 compatible magic header bytes and
 155     padding needed to implement PKCS1-v1_5.
 156
 157     Args:
 158       msg: The message to sign.
 159       modulus_size: The size of the key (in bits) used.
 160     Returns:
 161       The byte sequence of the message to be signed.
 162     """
 163     magic_sha256_header = [0x30, 0x31, 0x30, 0xd, 0x6, 0x9, 0x60, 0x86, 0x48,
 164                            0x1, 0x65, 0x3, 0x4, 0x2, 0x1, 0x5, 0x0, 0x4, 0x20]
 165
 166     hash_of_msg = hashlib.sha256(msg).digest() #???
 167
 168     self._Log(logf, 'sha256 digest of msg %s: %s' % (msg, hash_of_msg))
 169
 170     encoded = bytes(magic_sha256_header) + hash_of_msg
 171     msg_size_bits = modulus_size + 8-(modulus_size % 8)  # Round up to next byte
 172
 173     pad_string = b'\xFF' * (msg_size_bits // 8 - len(encoded) - 3)
 174     return b'\x00\x01' + pad_string + b'\x00' + encoded
 175
 176   def _Log(self, logf, s):
 177     """Append message to log if log exists."""
 178     print(s)
 179     if logf:
 180       logf(s + '\n')
 181
 182   def Sign(self, bytes_to_sign, logf=None):
 183     """Signs the bytes using PKCS-v1_5.
 184
 185     Args:
 186       bytes_to_sign: The bytes to be signed.
 187     Returns:
 188       The signature in base64url encoded format.
 189     """
 190     # Implements PKCS1-v1_5 w/SHA256 over the bytes, and returns
 191     # the result as a base64url encoded bignum.
 192
 193     self._Log(logf, 'bytes_to_sign = %s' % bytes_to_sign)
 194     self._Log(logf, 'len = %d' % len(bytes_to_sign))
 195
 196     self._Log(logf, 'keypair size : %s' % self.keypair.size())
 197
 198     # Generate the PKCS1-v1_5 compatible message, which includes
 199     # magic ASN.1 bytes and padding:
 200     emsa_msg = self._MakeEmsaMessageSha256(bytes_to_sign, self.keypair.size(), logf)
 201     # TODO(jpanzer): Check whether we need to use max keysize above
 202     # or just keypair.size
 203
 204     self._Log(logf, 'emsa_msg = %s' % emsa_msg)
 205
 206     # Compute the signature:
 207     signature_long = self.keypair.sign(emsa_msg, None)[0]
 208
 209     # Encode the signature as armored text:
 210     signature_bytes = number.long_to_bytes(signature_long)
 211
 212     self._Log(logf, 'signature_bytes = [%s]' % signature_bytes)
 213
 214     return base64.urlsafe_b64encode(signature_bytes)
 215
 216   def Verify(self, signed_bytes, signature_b64):
 217     """Determines the validity of a signature over a signed buffer of bytes.
 218
 219     Args:
 220       signed_bytes: string The buffer of bytes the signature_b64 covers.
 221       signature_b64: string The putative signature, base64-encoded, to check.
 222     Returns:
 223       True if the request validated, False otherwise.
 224     """
 225     # Generate the PKCS1-v1_5 compatible message, which includes
 226     # magic ASN.1 bytes and padding:
 227     emsa_msg = self._MakeEmsaMessageSha256(signed_bytes,
 228                                            self.keypair.size())
 229
 230     # Get putative signature:
 231     putative_signature = base64.urlsafe_b64decode(signature_b64)
 232     putative_signature = number.bytes_to_long(putative_signature)
 233
 234     # Verify signature given public key:
 235     return self.keypair.verify(emsa_msg, (putative_signature,))