From a315223f98fa6f1fdea2b1080c5f3e33352ebb13 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Joachim=20Stro=CC=88mbergson?= Date: Mon, 27 Apr 2015 11:17:08 +0200 Subject: Updating modexp core to v 0.50. This version contains a working core that can perform sign and verify with big keys/values. The core builds ok in Altera and Xilinx FPGA tools. This commit also includes a new testgenerator capable of generating testbench for modexp with autgenerated test data of different lengths. The README has been updated with status and implementation results in for different FPGA devices. --- src/model/python/modexp.py | 203 +++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 203 insertions(+) create mode 100755 src/model/python/modexp.py (limited to 'src/model/python/modexp.py') diff --git a/src/model/python/modexp.py b/src/model/python/modexp.py new file mode 100755 index 0000000..97aab0b --- /dev/null +++ b/src/model/python/modexp.py @@ -0,0 +1,203 @@ +#!/usr/bin/env python3 +# -*- coding: utf-8 -*- +#======================================================================= +# +# modexp.py +# --------- +# A python model for doing modular exponention. +# +# +# Author: Joachim Strömbergson +# Copyright (c) 2014, Secworks Sweden AB +# +# Redistribution and use in source and binary forms, with or +# without modification, are permitted provided that the following +# conditions are met: +# +# 1. Redistributions of source code must retain the above copyright +# notice, this list of conditions and the following disclaimer. +# +# 2. 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. +# +# 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 OWNER 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 +#======================================================================= -- cgit v1.2.3