diff options
Diffstat (limited to 'rsa/common.py')
-rw-r--r-- | rsa/common.py | 69 |
1 files changed, 36 insertions, 33 deletions
diff --git a/rsa/common.py b/rsa/common.py index 39feb8c..bdbc90a 100644 --- a/rsa/common.py +++ b/rsa/common.py @@ -14,11 +14,11 @@ # See the License for the specific language governing permissions and # limitations under the License. -'''Common functionality shared by several modules.''' +"""Common functionality shared by several modules.""" def bit_size(num): - ''' + """ Number of bits needed to represent a integer excluding any prefix 0 bits. @@ -26,7 +26,7 @@ def bit_size(num): to match the behavior of the Python 3 API. Usage:: - + >>> bit_size(1023) 10 >>> bit_size(1024) @@ -40,7 +40,7 @@ def bit_size(num): before the number's bit length is determined. :returns: Returns the number of bits in the integer. - ''' + """ if num == 0: return 0 if num < 0: @@ -51,23 +51,23 @@ def bit_size(num): hex_num = "%x" % num return ((len(hex_num) - 1) * 4) + { - '0':0, '1':1, '2':2, '3':2, - '4':3, '5':3, '6':3, '7':3, - '8':4, '9':4, 'a':4, 'b':4, - 'c':4, 'd':4, 'e':4, 'f':4, - }[hex_num[0]] + '0': 0, '1': 1, '2': 2, '3': 2, + '4': 3, '5': 3, '6': 3, '7': 3, + '8': 4, '9': 4, 'a': 4, 'b': 4, + 'c': 4, 'd': 4, 'e': 4, 'f': 4, + }[hex_num[0]] def _bit_size(number): - ''' + """ Returns the number of bits required to hold a specific long number. - ''' + """ if number < 0: raise ValueError('Only nonnegative numbers possible: %s' % number) if number == 0: return 0 - + # This works, even with very large numbers. When using math.log(number, 2), # you'll get rounding errors and it'll fail. bits = 0 @@ -79,9 +79,9 @@ def _bit_size(number): def byte_size(number): - ''' + """ Returns the number of bytes required to hold a specific long number. - + The number of bytes is rounded up. Usage:: @@ -97,17 +97,17 @@ def byte_size(number): An unsigned integer :returns: The number of bytes required to hold a specific long number. - ''' + """ quanta, mod = divmod(bit_size(number), 8) if mod or number == 0: quanta += 1 return quanta - #return int(math.ceil(bit_size(number) / 8.0)) + # return int(math.ceil(bit_size(number) / 8.0)) def extended_gcd(a, b): - '''Returns a tuple (r, i, j) such that r = gcd(a, b) = ia + jb - ''' + """Returns a tuple (r, i, j) such that r = gcd(a, b) = ia + jb + """ # r = gcd(a,b) i = multiplicitive inverse of a mod b # or j = multiplicitive inverse of b mod a # Neg return values for i or j are made positive mod b or a respectively @@ -116,26 +116,28 @@ def extended_gcd(a, b): y = 1 lx = 1 ly = 0 - oa = a #Remember original a/b to remove - ob = b #negative values from return results + oa = a # Remember original a/b to remove + ob = b # negative values from return results while b != 0: q = a // b - (a, b) = (b, a % b) - (x, lx) = ((lx - (q * x)),x) - (y, ly) = ((ly - (q * y)),y) - if (lx < 0): lx += ob #If neg wrap modulo orignal b - if (ly < 0): ly += oa #If neg wrap modulo orignal a - return (a, lx, ly) #Return only positive values + (a, b) = (b, a % b) + (x, lx) = ((lx - (q * x)), x) + (y, ly) = ((ly - (q * y)), y) + if lx < 0: + lx += ob # If neg wrap modulo orignal b + if ly < 0: + ly += oa # If neg wrap modulo orignal a + return a, lx, ly # Return only positive values def inverse(x, n): - '''Returns x^-1 (mod n) + """Returns x^-1 (mod n) >>> inverse(7, 4) 3 >>> (inverse(143, 4) * 143) % 4 1 - ''' + """ (divider, inv, _) = extended_gcd(x, n) @@ -146,14 +148,14 @@ def inverse(x, n): def crt(a_values, modulo_values): - '''Chinese Remainder Theorem. + """Chinese Remainder Theorem. Calculates x such that x = a[i] (mod m[i]) for each i. :param a_values: the a-values of the above equation :param modulo_values: the m-values of the above equation :returns: x such that x = a[i] (mod m[i]) for each i - + >>> crt([2, 3], [3, 5]) 8 @@ -163,10 +165,10 @@ def crt(a_values, modulo_values): >>> crt([2, 3, 0], [7, 11, 15]) 135 - ''' + """ m = 1 - x = 0 + x = 0 for modulo in modulo_values: m *= modulo @@ -179,7 +181,8 @@ def crt(a_values, modulo_values): return x + if __name__ == '__main__': import doctest - doctest.testmod() + doctest.testmod() |