#!/usr/bin/env python3
# -*- coding: utf-8 -*-
#=======================================================================
#
# modexp.py
# ---------
# A python model for doing modular exponention.
#
#
# Author: Joachim Strömbergson
# Copyright (c) 2014, NORDUnet A/S
# All rights reserved.
#
# Redistribution and use in source and binary forms, with or without
# modification, are permitted provided that the following conditions are
# met:
# - Redistributions of source code must retain the above copyright notice,
#   this list of conditions and the following disclaimer.
#
# - Redistributions in binary form must reproduce the above copyright
#   notice, this list of conditions and the following disclaimer in the
#   documentation and/or other materials provided with the distribution.
#
# - Neither the name of the NORDUnet nor the names of its contributors may
#   be used to endorse or promote products derived from this software
#   without specific prior written permission.
#
# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
# IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
# TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
# PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
# HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
# SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
# TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
# PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
# LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
# NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
# SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
#
#=======================================================================

#-------------------------------------------------------------------
# Python module imports.
#-------------------------------------------------------------------
import sys


#-------------------------------------------------------------------
# Defines.
#-------------------------------------------------------------------
VERBOSE = False


#-------------------------------------------------------------------
# iter_mult()
#
# Iterative multiplier (i*j) with operands that are bitlen
# number of bits.
#-------------------------------------------------------------------
def iter_mult(i, j, bitlen):
    print("Mult of 0x%08x and 0x%08x of max 0x%08x bits" %
          (i, j, bitlen))

    r = 0
    max = 2**bitlen - 1

    for bit in range(bitlen):
        mask = ((j & (1 << bit)))
        r = (r + (i * mask)) & max
        print("bit: 0x%08x, mask = 0x%01x, r = 0x%08x" %
              (bit, mask, r))
    return r


#-------------------------------------------------------------------
# iter_exp()
#
# Iterative exponentiator (i ** j) with operands that are
# bitlen number of bits.
#-------------------------------------------------------------------
def iter_exp(i, j, bitlen):
    print("Exp of 0x%08x and 0x%08x of max 0x%08x bits" %
          (i, j, bitlen))

    n = i
    for bit in range(j):
        n = iter_mult(n, n, bitlen)
    return n


#-------------------------------------------------------------------
# gen_keypair()
#
# Generate a keypair (and exponent) with n bits in length.
#-------------------------------------------------------------------
def gen_keypair(bitlen):
    print("Generating keys with %d bits" % (bitlen))
    print("")

    e = 3
    pub = 2**bitlen - 1
    priv = pub - 2

    return (pub, priv, e)


#-------------------------------------------------------------------
# keytest()
#-------------------------------------------------------------------
def keytest():
    print("key encryption and decryption")
    print("-----------------------------")

    p = 11
    q = 13
    n = p * q
    tiotent = (p - 1) * (q - 1)

    print("p = %d, q = %d, n = %d, tiotent = %d" % (p, q, n, tiotent))

    e = 7
    d = 103

    print("e = %d, d = %d" % (e, d))

    print("Public key: e, n = %d, %d" % (e, n))
    print("private key: d = %d" % (d))

    m = 9
    cm = modexp(m, e, n)
    m2 = modexp(cm, d, n)
    print("Encryption of message m  = %d -> cm = %d" % (m, cm))
    print("Decryption of message cm = %d -> m  = %d" % (cm, m2))


#-------------------------------------------------------------------
# modtest()
#-------------------------------------------------------------------
def modtest():
    print("modular exponentition")
    print("---------------------")

    M = 12345
    e = 3
    N = 12347

    print("M = %d, e = %d, N = %d" % (M, e, N))
    print(modexp(M, e, N))
    print("")

    M = 2**8192 - 37
    e = 3
    N = 2**8192 - 1

    print("M = %d, e = %d, N = %d" % (M, e, N))
    print(modexp(M, e, N))
    print("")


#-------------------------------------------------------------------
# modexp()
#
# Perform generic modular exponention of the given message M
# using the exponent e and modulus N.
#-------------------------------------------------------------------
def modexp(M, e, N):
    return (M ** e) % N


#-------------------------------------------------------------------
# main()
#
# Parse any arguments and run the tests.
#-------------------------------------------------------------------
def main():
#    my_keypair = gen_keypair(12)
#    print(my_keypair)
#    modtest()
#    keytest()

    # test of iterative multiply.
    print(iter_mult(2, 3, 4))
    print(iter_mult(2, 3, 5))
    print(iter_mult(2543, 1201, 12))
    print(iter_mult(2543, 1201, 16))
    print(iter_mult(2543, 1201, 23))

    # test of iterative exponentiation.
    print(iter_exp(2, 3, 12))
    print(iter_exp(8, 8, 4))


#-------------------------------------------------------------------
# __name__
# Python thingy which allows the file to be run standalone as
# well as parsed from within a Python interpreter.
#-------------------------------------------------------------------
if __name__=="__main__":
    # Run the main function.
    sys.exit(main())


#=======================================================================
# EOF modexp.py
#=======================================================================