bn.py

# Copyright 2010 Dolphin Emulator Project
# Licensed under GPLv2+

# Copyright 2007,2008  Segher Boessenkool  <segher@kernel.crashing.org>
# Licensed under the terms of the GNU GPL, version 2
# http://www.gnu.org/licenses/old-licenses/gpl-2.0.txt

# Ported to Python by Seeky

def zero(d, n):
    for i in range(0, n):
        d[i] = 0

def copy(d, a, n):
    d[:n] = a[:n]

def compare(a, b, n):
    for i in range(0, n):
        if a[i] > b[i]:
            return 1
        if a[i] < b[i]:
            return -1
    return 0

def sub_modulus(a, N, n):
    c = 0
    for i in range(n - 1, -1, -1):
        dig = N[i] + c
        c = (a[i] < dig)
        a[i] = (a[i] - dig) & 0xff
    
def add(d, a, b, N, n):
    c = 0
    for i in range(n - 1, -1, -1):
        dig = a[i] + b[i] + c
        c = (dig >= 0x100)
        d[i] = dig & 0xff

    if c:
        sub_modulus(d, N, n)
    if compare(d, N, n) >= 0:
        sub_modulus(d, N, n)

def mul(d, a, b, N, n):
    zero(d, n)

    for i in range(0, n):
        mask = 0x80
        while mask != 0:
            add(d, d, d, N, n)
            if a[i] & mask:
                add(d, d, b, N, n)
            mask >>= 1

def exp(d, a, N, n, e, en):
    t = bytearray(512)
    zero(d, n)
    d[n - 1] = 1
    for i in range(0, en):
        mask = 0x80
        while mask != 0:
            mul(t, d, d, N, n)
            if e[i] & mask:
                mul(d, t, a, N, n)
            else:
                copy(d, t, n)
            mask >>= 1

def inv(d, a, N, n):
    t = bytearray(512)
    s = bytearray(512)

    copy(t, N, n)
    zero(s, n)
    s[n - 1] = 2
    sub_modulus(t, s, n)
    exp(d, a, N, n, t, n)