Fork me on GitHub

Python实现RSA和ECC

Python3实现RSA和ECC非对称加密算法。

In [ ]:
print('python3')

公钥密码算法的编写

本实验是使用python来实现RSA和ECC公钥加密算法,并对加密解密过程的正确性进行验证。 最后,和上一节的对称加密算法进行比较。

1.实验目的

  1. 掌握非对称加密体制原理
  2. 掌握RSA、ECC公钥算法的实现方法,能对其安全性进行分析
  3. 了解公钥密码体制的应用

2.实验工具

  • Jupyter Notebook
  • Python3.5

3.实验环境

  • Ubuntu16.04LTS操作系统
  • Python3标准库

4.实验步骤

4.1 回顾课程,查阅资料

4.2 非对称加密与对称加密比较

A和C要传输数据,但数据需要经过B
加密要解决两个基本问题

  • B 能看到 A 发给 C 的内容。
  • B 可以伪造 A 发给 C 的内容。

对称加密虽然解决了前面的两个问题,却带来新问题:
加解密算法得以实现,依赖于 A 与 C 的单独协商,这与前面说的 A 与 C 通信必须经过 B 的前提矛盾。即使这种单独协商偶尔可以实现,它的机会也必定十分稀缺。如果需要与 C 通信的不止一个 A,而是 A0、A1……An,每个 Ai 都要避开其它所有节点与 C 单独协商,这是不现实的。 如果让这些 A0、A1……An都使用同样的算法呢?显然,每个 Ai 都会知道它不该知道的信息,也可以冒充其它 Ai 发送信息。
所以,每两个节点之间要有一套专用的加解密算法,如果一个网络上有 N 个节点,一共要有 N *(N-1)/2 套算法。对于动辄成千上万个节点的网络,这个数字太大了。

人们发现,前述问题的症结在于对称。

如果加密算法和解密算法无法互相推导,事情就好办了:
所有发给 C 的信息都用同样的加密算法,而只有 C 自己才能解密。Ai 虽然懂得加密,但并不能从加密算法推导出解密算法来。因此一个 Ai 发给 C 的信息不会泄露给其它 Ai,就连加密者自己也不会解密。 现在,对于每个节点,只要制作一套加解密算法,解密算法自己留着,将加密算法公布出去:谁想发消息给我就用这个方法加密,加密之后只有我能解密,别人谁也解不出来。加密算法是公开的,大家都知道,不需要与每个节点单独协商了。

4.3.RSA算法介绍

RSA 算法的实质是三个自然数,一般记作 n, d, e。n 和 d 构成一个密钥,n 和 e 构成另一个密钥。 对于(n, d)与(n, e)这两个密钥,无论用哪个密钥加密出来的密文都可以用另一个密钥解开, 所以不必强调哪个用于加密,哪个用于解密,只要把一个公布出去(称为公钥),另一个自己藏着(称为私钥)就行了。

4.3.1 生成公钥和私钥

假设Alice想要通过一个不可靠的媒体接收Bob的一条私人消息。她可以用以下的方式来产生一个公钥和一个私钥:

  1. 随意选择两个大的质数$p$和$q$,$p$不等于$q$,计算$N=pq$。
  2. 根据欧拉函数,求得${\displaystyle r=\varphi (N)=\varphi (p)\varphi (q)=(p-1)(q-1)}$
  3. 选择一个小于 ${\displaystyle r}$ 的整数${\displaystyle e}$,使 ${\displaystyle e}与{\displaystyle r}$ 互质。并求得 ${\displaystyle e}关于{\displaystyle r}$的模反元素,命名为${\displaystyle d}(求{\displaystyle d}令{\displaystyle ed\equiv 1{\pmod {r}}}$)。
    (模反元素存在,当且仅当${\displaystyle e}与{\displaystyle r}$互质)
  4. 将 ${\displaystyle p}和 {\displaystyle q}$的记录销毁。

${\displaystyle (N,e)}是公钥, {\displaystyle (N,d)}是私钥。Alice将她的公钥 {\displaystyle (N,e)}传给Bob,而将她的私钥 {\displaystyle (N,d)}$藏起来。

4.3.2 加密消息

假设Bob想给Alice送一个消息 ${\displaystyle m},他知道Alice产生的 {\displaystyle N}和 {\displaystyle e}。他使用起先与Alice约好的格式将 {\displaystyle m}转换为一个小于 {\displaystyle N}的非负整数 {\displaystyle n},比如他可以将每一个字转换为这个字的Unicode码,然后将这些数字连在一起组成一个数字。假如他的信息非常长的话,他可以将这个信息分为几段,然后将每一段转换为 {\displaystyle n}。用下面这个公式他可以将 {\displaystyle n}加密为 {\displaystyle c}$:

${\displaystyle c\equiv n^{e}{\pmod {N}}} 计算 {\displaystyle c}并不复杂。Bob算出 {\displaystyle c}$后就可以将它传递给Alice。

4.3.3 解密消息

公钥解密

4.3.4 签名消息

RSA也可以用来为一个消息署名。假如Alice想给Bob传递一个署名的消息的话,那么她可以为她的消息计算一个散列值(Message digest),然后用她的私钥“加密”(如同前面“加密消息”的步骤)这个散列值并将这个“署名”加在消息的后面。这个消息只有用她的公钥才能被解密。Bob获得这个消息后可以用Alice的公钥“解密”(如同前面“解密消息”的步骤)这个散列值,然后将这个数据与他自己为这个消息计算的散列值相比较。假如两者相符的话,那么Bob就可以知道发信人持有Alice的私钥,以及这个消息在传播路径上没有被篡改过。

4.4 编写RSA加密解密的测试用例

if __name__ == '__main__':
    # 测试已知数据
    public = PublicKey(n=2534665157, e=7)
    private = PrivateKey(n=2534665157, d=1810402843)

    assert public.encrypt(123) == 2463995467
    assert public.encrypt(456) == 2022084991
    assert public.encrypt(123456) == 1299565302

    assert private.decrypt(2463995467) == 123
    assert private.decrypt(2022084991) == 456
    assert private.decrypt(1299565302) == 123456
    # 测试随机数据
    for length in range(4, 17):
        public, private = make_key_pair(length)

        assert public.n == private.n
        assert len(bin(public.n)) - 2 == length

        x = random.randrange(public.n - 2)
        y = public.encrypt(x)
        assert private.decrypt(y) == x

        assert public.encrypt(public.n - 1) == public.n - 1
        assert public.encrypt(public.n) == 0
        assert private.decrypt(public.n - 1) == public.n - 1
        assert private.decrypt(public.n) == 0
    print('验证完毕')

4.5 ECC算法原理

椭圆曲线密码学的许多形式有稍微的不同,所有的都依赖于被广泛承认的解决椭圆曲线离散对数问题的困难性上,对应有限域上椭圆曲线的群。

对于ECC系统来说,完成运行系统所必须的群操作比同样大小的因数分解系统或模整数离散对数系统要慢。不过,ECC系统的拥护者相信ECDLP问题比DLP或因数分解问题要难的多,并且因此使用ECC能用小的多的密钥长度来提供同等的安全,在这方面来说它确实比例如RSA之类的更快。到目前为止已经公布的结果趋于支持这个结论,不过一些专家表示怀疑。

4.6 编写ECC算法的测试代码

4.7 编写RSA和ECC公钥加密的python实现,并进行测试验证

代码和测试结果在报告最后

4.8 总结实验,编写实验报告

5. 实验总结

  • 需要善于借鉴前人经验,搜集资料
  • 实验只支持ascii码,对其他字符编码没有解决
  • 利用优秀的工具,如Jupyter可以提高学习效率

6. 实验完整代码

In [5]:
"""RSA加密系统的简单实现

模块展示了一种简单清晰的RSA算法的实现,它的目的不是效率,而是为了可读性。

The usage is simple. First, create a random key pair:

    >>> public_key, private_key = make_key_pair(8)

The number 8 is the _key length_. The higher this number, the stronger the
encryption. The public key can be used to encrypt a message (in this module,
a message is simply a positive integer number):

    >>> message = 5
    >>> encrypted_message = public_key.encrypt(message)

The encrypted information can be retrieved only with the private key:

    >>> private_key.decrypt(encrypted_message)
    5

Private and public keys are made of three numeric parameters: ``n``, ``d`` and
``e``. ``n`` has the bit length specified with ``make_key_pair`` and is shared
between the two keys; ``e`` is used by the public key encrypt; ``d`` is used
by the private key to decrypt.

It's worth noting that ``n - 2`` is the highest number that can be safely
encrypted or decrypted. For example, encrypting (or decrypting) the number
``n - 1`` does nothing, and encrypting (or decrypting) the number ``n`` always
returns 0.

    >>> key = PublicKey(n=143, e=113)
    >>> key.encrypt(142)  # n - 1
    142
    >>> key.encrypt(143)  # n
    0

Also encrypting (or decrypting) 0 or 1 always returns 0 or 1:

    >>> key.encrypt(0)
    0
    >>> key.encrypt(1)
    1

Note that sometimes the original and the encrypted messages are the same, as
shown in the following example:

    >>> for x in range(143):  # n
    ...     if key.encrypt(x) == x:
    ...         print(x)
    0
    1
    12
    21
    34
    44
    65
    66
    77
    78
    99
    109
    122
    131
    142

"""
import random
from collections import namedtuple


def get_primes(start, stop):
    """Return a list of prime numbers in ``range(start, stop)``."""
    if start >= stop:
        return []

    primes = [2]

    for n in range(3, stop + 1, 2):
        for p in primes:
            if n % p == 0:
                break
        else:
            primes.append(n)

    while primes and primes[0] < start:
        del primes[0]

    return primes


def are_relatively_prime(a, b):
    """Return ``True`` if ``a`` and ``b`` are two relatively prime numbers.

    Two numbers are relatively prime if they share no common factors,
    i.e. there is no integer (except 1) that divides both.
    """
    for n in range(2, min(a, b) + 1):
        if a % n == b % n == 0:
            return False
    return True


def make_key_pair(length):
    """Create a public-private key pair.

    The key pair is generated from two random prime numbers. The argument
    ``length`` specifies the bit length of the number ``n`` shared between
    the two keys: the higher, the better.
    """
    if length < 4:
        raise ValueError('cannot generate a key of length less '
                         'than 4 (got {!r})'.format(length))

    # First step: find a number ``n`` which is the product of two prime
    # numbers (``p`` and ``q``). ``n`` must have the number of bits specified
    # by ``length``, therefore it must be in ``range(n_min, n_max + 1)``.
    n_min = 1 << (length - 1)
    n_max = (1 << length) - 1

    # The key is stronger if ``p`` and ``q`` have similar bit length. We
    # choose two prime numbers in ``range(start, stop)`` so that the
    # difference of bit lengths is at most 2.
    start = 1 << (length // 2 - 1)
    stop = 1 << (length // 2 + 1)
    primes = get_primes(start, stop)

    # Now that we have a list of prime number candidates, randomly select
    # two so that their product is in ``range(n_min, n_max + 1)``.
    while primes:
        p = random.choice(primes)
        primes.remove(p)
        q_candidates = [q for q in primes
                        if n_min <= p * q <= n_max]
        if q_candidates:
            q = random.choice(q_candidates)
            break
    else:
        raise AssertionError("cannot find 'p' and 'q' for a key of "
                             "length={!r}".format(length))

    # Second step: choose a number ``e`` lower than ``(p - 1) * (q - 1)``
    # which shares no factors with ``(p - 1) * (q - 1)``.
    stop = (p - 1) * (q - 1)
    for e in range(3, stop, 2):
        if are_relatively_prime(e, stop):
            break
    else:
        raise AssertionError("cannot find 'e' with p={!r} "
                             "and q={!r}".format(p, q))

    # Third step: find ``d`` such that ``(d * e - 1)`` is divisible by
    # ``(p - 1) * (q - 1)``.
    for d in range(3, stop, 2):
        if d * e % stop == 1:
            break
    else:
        raise AssertionError("cannot find 'd' with p={!r}, q={!r} "
                             "and e={!r}".format(p, q, e))

    # That's all. We can build and return the public and private keys.
    return PublicKey(p * q, e), PrivateKey(p * q, d)


class PublicKey(namedtuple('PublicKey', 'n e')):
    """Public key which can be used to encrypt data."""

    __slots__ = ()

    def encrypt(self, x):
        """Encrypt the number ``x``.

        The result is a number which can be decrypted only using the
        private key.
        """
        return pow(x, self.e, self.n)


class PrivateKey(namedtuple('PrivateKey', 'n d')):
    """Private key which can be used both to decrypt data."""

    __slots__ = ()

    def decrypt(self, x):
        """Decrypt the number ``x``.

        The argument ``x`` must be the result of the ``encrypt`` method of
        the public key.
        """
        return pow(x, self.d, self.n)


if __name__ == '__main__':
    # Test with known results.
    public = PublicKey(n=2534665157, e=7)
    private = PrivateKey(n=2534665157, d=1810402843)

    assert public.encrypt(123) == 2463995467
    assert public.encrypt(456) == 2022084991
    assert public.encrypt(123456) == 1299565302

    assert private.decrypt(2463995467) == 123
    assert private.decrypt(2022084991) == 456
    assert private.decrypt(1299565302) == 123456

    # Test with random values.
    for length in range(4, 17):
        public, private = make_key_pair(length)

        assert public.n == private.n
        assert len(bin(public.n)) - 2 == length

        x = random.randrange(public.n - 2)
        y = public.encrypt(x)
        assert private.decrypt(y) == x

        assert public.encrypt(public.n - 1) == public.n - 1
        assert public.encrypt(public.n) == 0
        assert private.decrypt(public.n - 1) == public.n - 1
        assert private.decrypt(public.n) == 0
    print('验证完毕')
验证完毕
In [7]:
# Basics of Elliptic Curve Cryptography implementation on Python
import collections


def inv(n, q):
    """div on PN modulo a/b mod q as a * inv(b, q) mod q
    >>> assert n * inv(n, q) % q == 1
    """
    # n*inv % q = 1 => n*inv = q*m + 1 => n*inv + q*-m = 1
    # => egcd(n, q) = (inv, -m, 1) => inv = egcd(n, q)[0] (mod q)
    return egcd(n, q)[0] % q
    #[ref] naive implementation
    #for i in range(q):
    #    if (n * i) % q == 1:
    #        return i
    #    pass
    #assert False, "unreached"
    #pass


def egcd(a, b):
    """extended GCD
    returns: (s, t, gcd) as a*s + b*t == gcd
    >>> s, t, gcd = egcd(a, b)
    >>> assert a % gcd == 0 and b % gcd == 0
    >>> assert a * s + b * t == gcd
    """
    s0, s1, t0, t1 = 1, 0, 0, 1
    while b > 0:
        q, r = divmod(a, b)
        a, b = b, r
        s0, s1, t0, t1 = s1, s0 - q * s1, t1, t0 - q * t1
        pass
    return s0, t0, a


def sqrt(n, q):
    """sqrt on PN modulo: returns two numbers or exception if not exist
    >>> assert (sqrt(n, q)[0] ** 2) % q == n
    >>> assert (sqrt(n, q)[1] ** 2) % q == n
    """
    assert n < q
    for i in range(1, q):
        if i * i % q == n:
            return (i, q - i)
        pass
    raise Exception("not found")


Coord = collections.namedtuple("Coord", ["x", "y"])


class EC(object):
    """System of Elliptic Curve"""
    def __init__(self, a, b, q):
        """elliptic curve as: (y**2 = x**3 + a * x + b) mod q
        - a, b: params of curve formula
        - q: prime number
        """
        assert 0 < a and a < q and 0 < b and b < q and q > 2
        assert (4 * (a ** 3) + 27 * (b ** 2))  % q != 0
        self.a = a
        self.b = b
        self.q = q
        # just as unique ZERO value representation for "add": (not on curve)
        self.zero = Coord(0, 0)
        pass

    def is_valid(self, p):
        if p == self.zero: return True
        l = (p.y ** 2) % self.q
        r = ((p.x ** 3) + self.a * p.x + self.b) % self.q
        return l == r

    def at(self, x):
        """find points on curve at x
        - x: int < q
        - returns: ((x, y), (x,-y)) or not found exception
        >>> a, ma = ec.at(x)
        >>> assert a.x == ma.x and a.x == x
        >>> assert a.x == ma.x and a.x == x
        >>> assert ec.neg(a) == ma
        >>> assert ec.is_valid(a) and ec.is_valid(ma)
        """
        assert x < self.q
        ysq = (x ** 3 + self.a * x + self.b) % self.q
        y, my = sqrt(ysq, self.q)
        return Coord(x, y), Coord(x, my)

    def neg(self, p):
        """negate p
        >>> assert ec.is_valid(ec.neg(p))
        """
        return Coord(p.x, -p.y % self.q)

    def add(self, p1, p2):
        """ of elliptic curve: negate of 3rd cross point of (p1,p2) line
        >>> d = ec.add(a, b)
        >>> assert ec.is_valid(d)
        >>> assert ec.add(d, ec.neg(b)) == a
        >>> assert ec.add(a, ec.neg(a)) == ec.zero
        >>> assert ec.add(a, b) == ec.add(b, a)
        >>> assert ec.add(a, ec.add(b, c)) == ec.add(ec.add(a, b), c)
        """
        if p1 == self.zero: return p2
        if p2 == self.zero: return p1
        if p1.x == p2.x and (p1.y != p2.y or p1.y == 0):
            # p1 + -p1 == 0
            return self.zero
        if p1.x == p2.x:
            # p1 + p1: use tangent line of p1 as (p1,p1) line
            l = (3 * p1.x * p1.x + self.a) * inv(2 * p1.y, self.q) % self.q
            pass
        else:
            l = (p2.y - p1.y) * inv(p2.x - p1.x, self.q) % self.q
            pass
        x = (l * l - p1.x - p2.x) % self.q
        y = (l * (p1.x - x) - p1.y) % self.q
        return Coord(x, y)

    def mul(self, p, n):
        """n times  of elliptic curve
        >>> m = ec.mul(p, n)
        >>> assert ec.is_valid(m)
        >>> assert ec.mul(p, 0) == ec.zero
        """
        r = self.zero
        m2 = p
        # O(log2(n)) add
        while 0 < n:
            if n & 1 == 1:
                r = self.add(r, m2)
                pass
            n, m2 = n >> 1, self.add(m2, m2)
            pass
        # [ref] O(n) add
        #for i in range(n):
        #    r = self.add(r, p)
        #    pass
        return r

    def order(self, g):
        """order of point g
        >>> o = ec.order(g)
        >>> assert ec.is_valid(a) and ec.mul(a, o) == ec.zero
        >>> assert o <= ec.q
        """
        assert self.is_valid(g) and g != self.zero
        for i in range(1, self.q + 1):
            if self.mul(g, i) == self.zero:
                return i
            pass
        raise Exception("Invalid order")
    pass


class ElGamal(object):
    """ElGamal Encryption
    pub key encryption as replacing (mulmod, powmod) to (ec.add, ec.mul)
    - ec: elliptic curve
    - g: (random) a point on ec
    """
    def __init__(self, ec, g):
        assert ec.is_valid(g)
        self.ec = ec
        self.g = g
        self.n = ec.order(g)
        pass

    def gen(self, priv):
        """generate pub key
        - priv: priv key as (random) int < ec.q
        - returns: pub key as points on ec
        """
        return self.ec.mul(g, priv)

    def enc(self, plain, pub, r):
        """encrypt
        - plain: data as a point on ec
        - pub: pub key as points on ec
        - r: randam int < ec.q
        - returns: (cipher1, ciper2) as points on ec
        """
        assert self.ec.is_valid(plain)
        assert self.ec.is_valid(pub)
        return (self.ec.mul(g, r), self.ec.add(plain, self.ec.mul(pub, r)))

    def dec(self, cipher, priv):
        """decrypt
        - chiper: (chiper1, chiper2) as points on ec
        - priv: private key as int < ec.q
        - returns: plain as a point on ec
        """
        c1, c2 = cipher
        assert self.ec.is_valid(c1) and ec.is_valid(c2)
        return self.ec.add(c2, self.ec.neg(self.ec.mul(c1, priv)))
    pass


class DiffieHellman(object):
    """Elliptic Curve Diffie Hellman (Key Agreement)
    - ec: elliptic curve
    - g: a point on ec
    """
    def __init__(self, ec, g):
        self.ec = ec
        self.g = g
        self.n = ec.order(g)
        pass

    def gen(self, priv):
        """generate pub key"""
        assert 0 < priv and priv < self.n
        return self.ec.mul(self.g, priv)

    def secret(self, priv, pub):
        """calc shared secret key for the pair
        - priv: my private key as int
        - pub: partner pub key as a point on ec
        - returns: shared secret as a point on ec
        """
        assert self.ec.is_valid(pub)
        assert self.ec.mul(pub, self.n) == self.ec.zero
        return self.ec.mul(pub, priv)
    pass


class DSA(object):
    """ECDSA
    - ec: elliptic curve
    - g: a point on ec
    """
    def __init__(self, ec, g):
        self.ec = ec
        self.g = g
        self.n = ec.order(g)
        pass

    def gen(self, priv):
        """generate pub key"""
        assert 0 < priv and priv < self.n
        return self.ec.mul(self.g, priv)

    def sign(self, hashval, priv, r):
        """generate signature
        - hashval: hash value of message as int
        - priv: priv key as int
        - r: random int 
        - returns: signature as (int, int)
        """
        assert 0 < r and r < self.n
        m = self.ec.mul(self.g, r)
        return (m.x, inv(r, self.n) * (hashval + m.x * priv) % self.n)

    def validate(self, hashval, sig, pub):
        """validate signature
        - hashval: hash value of message as int
        - sig: signature as (int, int)
        - pub: pub key as a point on ec
        """
        assert self.ec.is_valid(pub)
        assert self.ec.mul(pub, self.n) == self.ec.zero
        w = inv(sig[1], self.n)
        u1, u2 = hashval * w % self.n, sig[0] * w % self.n
        p = self.ec.add(self.ec.mul(self.g, u1), self.ec.mul(pub, u2))
        return p.x % self.n == sig[0]
    pass


if __name__ == "__main__":
    # shared elliptic curve system of examples
    ec = EC(1, 18, 19)
    g, _ = ec.at(7)
    assert ec.order(g) <= ec.q
    
    # ElGamal enc/dec usage
    eg = ElGamal(ec, g)
    # mapping value to ec point
    # "masking": value k to point ec.mul(g, k)
    # ("imbedding" on proper n:use a point of x as 0 <= n*v <= x < n*(v+1) < q)
    mapping = [ec.mul(g, i) for i in range(eg.n)]
    plain = mapping[7] 
    
    priv = 5
    pub = eg.gen(priv)
    
    cipher = eg.enc(plain, pub, 15)
    decoded = eg.dec(cipher, priv)
    assert decoded == plain
    assert cipher != pub
    
    
    # ECDH usage
    dh = DiffieHellman(ec, g)
    
    apriv = 11
    apub = dh.gen(apriv)
    
    bpriv = 3
    bpub = dh.gen(bpriv)
    
    cpriv = 7
    cpub = dh.gen(cpriv)
    # same secret on each pair
    assert dh.secret(apriv, bpub) == dh.secret(bpriv, apub)
    assert dh.secret(apriv, cpub) == dh.secret(cpriv, apub)
    assert dh.secret(bpriv, cpub) == dh.secret(cpriv, bpub)
    
    # not same secret on other pair
    assert dh.secret(apriv, cpub) != dh.secret(apriv, bpub)
    assert dh.secret(bpriv, apub) != dh.secret(bpriv, cpub)
    assert dh.secret(cpriv, bpub) != dh.secret(cpriv, apub)
    
    
    # ECDSA usage
    dsa = DSA(ec, g)
    
    priv = 11
    pub = eg.gen(priv)
    hashval = 128
    r = 7
    print('完成测试')
    sig = dsa.sign(hashval, priv, r)
    assert dsa.validate(hashval, sig, pub)
    pass
完成测试

Comments