Switch branches/tags
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
230 lines (190 sloc) 11.4 KB
from __future__ import division
import hashlib
from hkdf import Hkdf
from .six import integer_types
from .util import (size_bits, size_bytes, unbiased_randrange,
bytes_to_number, number_to_bytes)
"""Interface specification for a Group.
A cyclic abelian group, in the mathematical sense, is a collection of
'elements' and a (binary) operation that takes two elements and produces a
third. It has the following additional properties:
* there is an 'identity' element named 0, and X+0=X
* there is a distinguished 'generator' element G
* adding G to 0 'n' times is called scalar multiplication: Y=n*G
* this addition loops around after 'q' times, called the 'order'
* so (n+k*q)*X = n*X
* scalar multiplication is associative, n*(X+Y) = n*X+n*Y
* 'scalar division' is really multiplying by (q-n)
A 'scalar' is an integer in [0,q-1] inclusive. You can add scalars to each
other, invert them, and multiply them by elements. There is a one-to-one
mapping between scalars and elements. It is trivial to go from a scalar to an
element, but hard (in the cryptographic sense) to go from element to scalar.
You can ask for a random scalar, and you can convert scalars to bytes and
back again.
The form of an 'element' depends upon the group (there are integer-element
groups, and ECC groups). You can add elements together, invert them
(scalarmult by -1), and subtract them (invert then add). You can ask for a
random element (found by choosing a random scalar, then multiplying). You can
convert elements to bytes and back.
There is a distinguished element called 'Base', which is the generator
(or 'base point' in ECC groups).
Two final operations are provided. The first produces an 'arbitrary element'
from a seed. This is somewhat like a random element, but with the additional
important property that nobody knows what the corresponding scalar is. The
second takes a password (an arbitrary bytestring) and produces a scalar.
The functions that produce random scalars/elements require an entropy
function, which is expected to behave like os.urandom. The only reason to not
use os.urandom is for deterministic unit tests.
g = I2048Group # or Ed25519Group
s = g.random_scalar(entropy_f)
s = g.bytes_to_scalar(bytes)
bytes = g.scalar_to_bytes()
s = g.password_to_scalar(password)
e = g.bytes_to_element(bytes)
e = g.arbitrary_element(seed)
e = g.Base # this is an Element too, with all the methods below
e3 = e1.add(e2)
e3 = e1.scalarmult(s) # takes int, positive or negative
bytes = e.to_bytes()
# equality tests work: e1 == e2, e1 != e2
def expand_password(data, num_bytes):
h = Hkdf(salt=b"", input_key_material=data, hash=hashlib.sha256)
info = b"SPAKE2 pw"
return h.expand(info, num_bytes)
def password_to_scalar(pw, scalar_size_bytes, q):
assert isinstance(pw, bytes)
# the oversized hash reduces bias in the result, so
# uniformly-random passwords give nearly-uniform scalars
oversized = expand_password(pw, scalar_size_bytes+16)
assert len(oversized) >= scalar_size_bytes
i = bytes_to_number(oversized)
return i % q
def expand_arbitrary_element_seed(data, num_bytes):
h = Hkdf(salt=b"", input_key_material=data, hash=hashlib.sha256)
info = b"SPAKE2 arbitrary element"
return h.expand(info, num_bytes)
class _Element:
def __init__(self, group, e):
self._group = group
self._e = e
def add(self, other):
return self._group._add(self, other)
def scalarmult(self, s):
return self._group._scalarmult(self, s)
def to_bytes(self):
return self._group._element_to_bytes(self)
class IntegerGroup:
def __init__(self, p, q, g):
self.q = q # the subgroup order, used for scalars
self.scalar_size_bytes = size_bytes(self.q)
_s = self.scalar_to_bytes(self.password_to_scalar(b""))
assert isinstance(_s, bytes)
assert len(_s) >= self.scalar_size_bytes
self.Zero = _Element(self, 1)
self.Base = _Element(self, g) # generator of the subgroup
# these are the public system parameters
self.p = p # the field size
self.element_size_bits = size_bits(self.p)
self.element_size_bytes = size_bytes(self.p)
# double-check that the generator has the right order
assert pow(g, self.q, self.p) == 1
def order(self):
return self.q
def random_scalar(self, entropy_f):
return unbiased_randrange(0, self.q, entropy_f)
def scalar_to_bytes(self, i):
# both for hashing into transcript, and save/restore of
# intermediate state
assert isinstance(i, integer_types)
assert 0 <= 0 < self.q
return number_to_bytes(i, self.q)
def bytes_to_scalar(self, b):
# for restore of intermediate state
assert isinstance(b, bytes)
assert len(b) == self.scalar_size_bytes
i = bytes_to_number(b)
assert 0 <= i < self.q, (0, i, self.q)
return i
def password_to_scalar(self, pw):
return password_to_scalar(pw, self.scalar_size_bytes, self.q)
def arbitrary_element(self, seed):
# we do *not* know the discrete log of this one. Nobody should.
assert isinstance(seed, bytes)
processed_seed = expand_arbitrary_element_seed(seed,
assert isinstance(processed_seed, bytes)
assert len(processed_seed) == self.element_size_bytes
# The larger (non-prime-order) group (Zp*) we're using has order
# p-1. The smaller (prime-order) subgroup has order q. Subgroup
# orders always divide the larger group order, so r*q=p-1 for
# some integer r. If h is an arbitrary element of the larger
# group Zp*, then e=h^r will be an element of the subgroup. If h
# is selected uniformly at random, so will e, and nobody will
# know its discrete log. We can enforce this for pre-selected
# parameters by choosing h as the output of a hash function.
r = (self.p - 1) // self.q
assert r * self.q == self.p - 1
h = bytes_to_number(processed_seed) % self.p
element = _Element(self, pow(h, r, self.p))
assert self._is_member(element)
return element
def _is_member(self, e):
if not e._group is self:
return False
if pow(e._e, self.q, self.p) == 1:
return True
return False
def _element_to_bytes(self, e):
# for sending to other side, and hashing into transcript
assert isinstance(e, _Element)
assert e._group is self
return number_to_bytes(e._e, self.p)
def bytes_to_element(self, b):
# for receiving from other side: test group membership here
assert isinstance(b, bytes)
assert len(b) == self.element_size_bytes
i = bytes_to_number(b)
if i <= 0 or i >= self.p: # Zp* excludes 0
raise ValueError("alleged element not in the field")
e = _Element(self, i)
if not self._is_member(e):
raise ValueError("element is not in the right group")
return e
def _scalarmult(self, e1, i):
if not isinstance(e1, _Element):
raise TypeError("E*N requires E be an element")
assert e1._group is self
if not isinstance(i, integer_types):
raise TypeError("E*N requires N be a scalar")
return _Element(self, pow(e1._e, i % self.q, self.p))
def _add(self, e1, e2):
if not isinstance(e1, _Element):
raise TypeError("E*N requires E be an element")
assert e1._group is self
if not isinstance(e2, _Element):
raise TypeError("E*N requires E be an element")
assert e2._group is self
return _Element(self, (e1._e * e2._e) % self.p)
# This 1024-bit group originally came from the J-PAKE demo code,
# . That java code
# recommended these 2048 and 3072 bit groups from this NIST document:
# L=1024, N=160
I1024 = IntegerGroup(
# L=2048, N=224
I2048 = IntegerGroup(
# L=3072, N=256
I3072 = IntegerGroup(