# coding: utf-8
# PyGOST -- Pure Python GOST cryptographic functions library
-# Copyright (C) 2015-2019 Sergey Matveev <stargrave@stargrave.org>
+# Copyright (C) 2015-2020 Sergey Matveev <stargrave@stargrave.org>
#
# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
-# the Free Software Foundation, either version 3 of the License, or
-# (at your option) any later version.
+# the Free Software Foundation, version 3 of the License.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
#
# You should have received a copy of the GNU General Public License
# along with this program. If not, see <http://www.gnu.org/licenses/>.
-""" GOST R 34.10 public-key signature function.
+"""GOST R 34.10 public-key signature function.
This is implementation of GOST R 34.10-2001 (:rfc:`5832`), GOST R
34.10-2012 (:rfc:`7091`). The difference between 2001 and 2012 is the
from pygost.utils import modinvert
-MODE2SIZE = {
- 2001: 32,
- 2012: 64,
-}
+def point_size(point):
+ """Determine is it either 256 or 512 bit point
+ """
+ return (512 // 8) if point.bit_length() > 256 else (256 // 8)
class GOST3410Curve(object):
- """ GOST 34.10 validated curve
+ """GOST 34.10 validated curve
>>> curve = CURVES["id-GostR3410-2001-TestParamSet"]
>>> prv = prv_unmarshal(urandom(32))
>>> pub = public_key(curve, prv)
>>> verify(curve, pub, GOST341194(data).digest(), signature)
True
+
+ :param long p: characteristic of the underlying prime field
+ :param long q: elliptic curve subgroup order
+ :param long a, b: coefficients of the equation of the elliptic curve in
+ the canonical form
+ :param long x, y: the coordinate of the point P (generator of the
+ subgroup of order q) of the elliptic curve in
+ the canonical form
+ :param long e, d: coefficients of the equation of the elliptic curve in
+ the twisted Edwards form
"""
- def __init__(self, p, q, a, b, x, y):
+ def __init__(self, p, q, a, b, x, y, cofactor=1, e=None, d=None):
self.p = p
self.q = q
self.a = a
self.b = b
self.x = x
self.y = y
- r1 = self.y * self.y % self.p
- r2 = ((self.x * self.x + self.a) * self.x + self.b) % self.p
- if r1 != self._pos(r2):
+ self.cofactor = cofactor
+ self.e = e
+ self.d = d
+ if not self.contains((x, y)):
raise ValueError("Invalid parameters")
+ self._st = None
+
+ @property
+ def point_size(self):
+ return point_size(self.p)
- def _pos(self, v):
+ def pos(self, v):
+ """Make positive number
+ """
if v < 0:
return v + self.p
return v
+ def contains(self, point):
+ """Is point on the curve?
+
+ :type point: (long, long)
+ """
+ x, y = point
+ r1 = y * y % self.p
+ r2 = ((x * x + self.a) * x + self.b) % self.p
+ return r1 == self.pos(r2)
+
def _add(self, p1x, p1y, p2x, p2y):
if p1x == p2x and p1y == p2y:
# double
t = ((3 * p1x * p1x + self.a) * modinvert(2 * p1y, self.p)) % self.p
else:
- tx = self._pos(p2x - p1x) % self.p
- ty = self._pos(p2y - p1y) % self.p
+ tx = self.pos(p2x - p1x) % self.p
+ ty = self.pos(p2y - p1y) % self.p
t = (ty * modinvert(tx, self.p)) % self.p
- tx = self._pos(t * t - p1x - p2x) % self.p
- ty = self._pos(t * (p1x - tx) - p1y) % self.p
+ tx = self.pos(t * t - p1x - p2x) % self.p
+ ty = self.pos(t * (p1x - tx) - p1y) % self.p
return tx, ty
def exp(self, degree, x=None, y=None):
x, y = self._add(x, y, x, y)
return tx, ty
+ def st(self):
+ """Compute s/t parameters for twisted Edwards curve points conversion
+ """
+ if self.e is None or self.d is None:
+ raise ValueError("non twisted Edwards curve")
+ if self._st is not None:
+ return self._st
+ self._st = (
+ self.pos(self.e - self.d) * modinvert(4, self.p) % self.p,
+ (self.e + self.d) * modinvert(6, self.p) % self.p,
+ )
+ return self._st
+
CURVES = {
"GostR3410_2001_ParamSet_cc": GOST3410Curve(
x=bytes2long(hexdec("0000000000000000000000000000000000000000000000000000000000000000")),
y=bytes2long(hexdec("41ECE55743711A8C3CBF3783CD08C0EE4D4DC440D4641A8F366E550DFDB3BB67")),
),
- "id-GostR3410-2001-CryptoPro-XchA-ParamSet": GOST3410Curve(
- p=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFD97")),
- q=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF6C611070995AD10045841B09B761B893")),
- a=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFD94")),
- b=bytes2long(hexdec("00000000000000000000000000000000000000000000000000000000000000a6")),
- x=bytes2long(hexdec("0000000000000000000000000000000000000000000000000000000000000001")),
- y=bytes2long(hexdec("8D91E471E0989CDA27DF505A453F2B7635294F2DDF23E3B122ACC99C9E9F1E14")),
- ),
- "id-GostR3410-2001-CryptoPro-XchB-ParamSet": GOST3410Curve(
- p=bytes2long(hexdec("9B9F605F5A858107AB1EC85E6B41C8AACF846E86789051D37998F7B9022D759B")),
- q=bytes2long(hexdec("9B9F605F5A858107AB1EC85E6B41C8AA582CA3511EDDFB74F02F3A6598980BB9")),
- a=bytes2long(hexdec("9B9F605F5A858107AB1EC85E6B41C8AACF846E86789051D37998F7B9022D7598")),
- b=bytes2long(hexdec("000000000000000000000000000000000000000000000000000000000000805a")),
- x=bytes2long(hexdec("0000000000000000000000000000000000000000000000000000000000000000")),
- y=bytes2long(hexdec("41ECE55743711A8C3CBF3783CD08C0EE4D4DC440D4641A8F366E550DFDB3BB67")),
- ),
"id-tc26-gost-3410-2012-256-paramSetA": GOST3410Curve(
p=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFD97")),
q=bytes2long(hexdec("400000000000000000000000000000000FD8CDDFC87B6635C115AF556C360C67")),
b=bytes2long(hexdec("295F9BAE7428ED9CCC20E7C359A9D41A22FCCD9108E17BF7BA9337A6F8AE9513")),
x=bytes2long(hexdec("91E38443A5E82C0D880923425712B2BB658B9196932E02C78B2582FE742DAA28")),
y=bytes2long(hexdec("32879423AB1A0375895786C4BB46E9565FDE0B5344766740AF268ADB32322E5C")),
+ cofactor=4,
+ e=0x01,
+ d=bytes2long(hexdec("0605F6B7C183FA81578BC39CFAD518132B9DF62897009AF7E522C32D6DC7BFFB")),
+ ),
+ "id-tc26-gost-3410-2012-512-paramSetTest": GOST3410Curve(
+ p=bytes2long(hexdec("4531ACD1FE0023C7550D267B6B2FEE80922B14B2FFB90F04D4EB7C09B5D2D15DF1D852741AF4704A0458047E80E4546D35B8336FAC224DD81664BBF528BE6373")),
+ q=bytes2long(hexdec("4531ACD1FE0023C7550D267B6B2FEE80922B14B2FFB90F04D4EB7C09B5D2D15DA82F2D7ECB1DBAC719905C5EECC423F1D86E25EDBE23C595D644AAF187E6E6DF")),
+ a=7,
+ b=bytes2long(hexdec("1CFF0806A31116DA29D8CFA54E57EB748BC5F377E49400FDD788B649ECA1AC4361834013B2AD7322480A89CA58E0CF74BC9E540C2ADD6897FAD0A3084F302ADC")),
+ x=bytes2long(hexdec("24D19CC64572EE30F396BF6EBBFD7A6C5213B3B3D7057CC825F91093A68CD762FD60611262CD838DC6B60AA7EEE804E28BC849977FAC33B4B530F1B120248A9A")),
+ y=bytes2long(hexdec("2BB312A43BD2CE6E0D020613C857ACDDCFBF061E91E5F2C3F32447C259F39B2C83AB156D77F1496BF7EB3351E1EE4E43DC1A18B91B24640B6DBB92CB1ADD371E")),
),
"id-tc26-gost-3410-12-512-paramSetA": GOST3410Curve(
p=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFDC7")),
b=bytes2long(hexdec("B4C4EE28CEBC6C2C8AC12952CF37F16AC7EFB6A9F69F4B57FFDA2E4F0DE5ADE038CBC2FFF719D2C18DE0284B8BFEF3B52B8CC7A5F5BF0A3C8D2319A5312557E1")),
x=bytes2long(hexdec("E2E31EDFC23DE7BDEBE241CE593EF5DE2295B7A9CBAEF021D385F7074CEA043AA27272A7AE602BF2A7B9033DB9ED3610C6FB85487EAE97AAC5BC7928C1950148")),
y=bytes2long(hexdec("F5CE40D95B5EB899ABBCCFF5911CB8577939804D6527378B8C108C3D2090FF9BE18E2D33E3021ED2EF32D85822423B6304F726AA854BAE07D0396E9A9ADDC40F")),
+ cofactor=4,
+ e=0x01,
+ d=bytes2long(hexdec("9E4F5D8C017D8D9F13A5CF3CDF5BFE4DAB402D54198E31EBDE28A0621050439CA6B39E0A515C06B304E2CE43E79E369E91A0CFC2BC2A22B4CA302DBB33EE7550")),
),
}
+CURVES["id-GostR3410-2001-CryptoPro-XchA-ParamSet"] = CURVES["id-GostR3410-2001-CryptoPro-A-ParamSet"]
+CURVES["id-GostR3410-2001-CryptoPro-XchB-ParamSet"] = CURVES["id-GostR3410-2001-CryptoPro-C-ParamSet"]
+CURVES["id-tc26-gost-3410-2012-256-paramSetB"] = CURVES["id-GostR3410-2001-CryptoPro-A-ParamSet"]
+CURVES["id-tc26-gost-3410-2012-256-paramSetC"] = CURVES["id-GostR3410-2001-CryptoPro-B-ParamSet"]
+CURVES["id-tc26-gost-3410-2012-256-paramSetD"] = CURVES["id-GostR3410-2001-CryptoPro-C-ParamSet"]
DEFAULT_CURVE = CURVES["id-GostR3410-2001-CryptoPro-A-ParamSet"]
def public_key(curve, prv):
- """ Generate public key from the private one
+ """Generate public key from the private one
:param GOST3410Curve curve: curve to use
:param long prv: private key
return curve.exp(prv)
-def sign(curve, prv, digest, mode=2001):
- """ Calculate signature for provided digest
+def sign(curve, prv, digest, rand=None):
+ """Calculate signature for provided digest
:param GOST3410Curve curve: curve to use
:param long prv: private key
:param digest: digest for signing
:type digest: bytes, 32 or 64 bytes
- :returns: signature
+ :param rand: optional predefined random data used for k/r generation
+ :type rand: bytes, 32 or 64 bytes
+ :returns: signature, BE(S) || BE(R)
:rtype: bytes, 64 or 128 bytes
"""
- size = MODE2SIZE[mode]
+ size = curve.point_size
q = curve.q
e = bytes2long(digest) % q
if e == 0:
e = 1
while True:
- k = bytes2long(urandom(size)) % q
+ if rand is None:
+ rand = urandom(size)
+ elif len(rand) != size:
+ raise ValueError("rand length != %d" % size)
+ k = bytes2long(rand) % q
if k == 0:
continue
r, _ = curve.exp(k)
return long2bytes(s, size) + long2bytes(r, size)
-def verify(curve, pub, digest, signature, mode=2001):
- """ Verify provided digest with the signature
+def verify(curve, pub, digest, signature):
+ """Verify provided digest with the signature
:param GOST3410Curve curve: curve to use
:type pub: (long, long)
:type signature: bytes, 64 or 128 bytes
:rtype: bool
"""
- size = MODE2SIZE[mode]
+ size = curve.point_size
if len(signature) != size * 2:
raise ValueError("Invalid signature length")
q = curve.q
def prv_unmarshal(prv):
- """Unmarshal private key
+ """Unmarshal little-endian private key
:param bytes prv: serialized private key
:rtype: long
return bytes2long(prv[::-1])
-def pub_marshal(pub, mode=2001):
+def pub_marshal(pub):
"""Marshal public key
:type pub: (long, long)
:rtype: bytes
+ :returns: LE(X) || LE(Y)
"""
- size = MODE2SIZE[mode]
+ size = point_size(pub[0])
return (long2bytes(pub[1], size) + long2bytes(pub[0], size))[::-1]
-def pub_unmarshal(pub, mode=2001):
+def pub_unmarshal(pub):
"""Unmarshal public key
+ :param pub: LE(X) || LE(Y)
:type pub: bytes
:rtype: (long, long)
"""
- size = MODE2SIZE[mode]
+ size = len(pub) // 2
pub = pub[::-1]
return (bytes2long(pub[size:]), bytes2long(pub[:size]))
+
+
+def uv2xy(curve, u, v):
+ """Convert twisted Edwards curve U,V coordinates to Weierstrass X,Y
+ """
+ s, t = curve.st()
+ k1 = (s * (1 + v)) % curve.p
+ k2 = curve.pos(1 - v)
+ x = t + k1 * modinvert(k2, curve.p)
+ y = k1 * modinvert(u * k2, curve.p)
+ return x % curve.p, y % curve.p
+
+
+def xy2uv(curve, x, y):
+ """Convert Weierstrass X,Y coordinates to twisted Edwards curve U,V
+ """
+ s, t = curve.st()
+ xmt = curve.pos(x - t)
+ u = xmt * modinvert(y, curve.p)
+ v = curve.pos(xmt - s) * modinvert(xmt + s, curve.p)
+ return u % curve.p, v % curve.p