Appendix B.  Point Verification Script

   The points from Appendix A.1 were generated with the following point
   verification script in Python:

curvesParams = [
{
"OID":"id-GostR3410-2001-CryptoPro-A-ParamSet",
"p":0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFD97,
"a":0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFD94,
"b":166,
"m":0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF6C611070995AD10045841B09B761B893,
"q":0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF6C611070995AD10045841B09B761B893,
"x":1,
"y":0x8D91E471E0989CDA27DF505A453F2B7635294F2DDF23E3B122ACC99C9E9F1E14,
"n":32
},
{
"OID":"id-GostR3410-2001-CryptoPro-B-ParamSet",
"p":0x8000000000000000000000000000000000000000000000000000000000000C99,
"a":0x8000000000000000000000000000000000000000000000000000000000000C96,
"b":0x3E1AF419A269A5F866A7D3C25C3DF80AE979259373FF2B182F49D4CE7E1BBC8B,
"m":0x800000000000000000000000000000015F700CFFF1A624E5E497161BCC8A198F,
"q":0x800000000000000000000000000000015F700CFFF1A624E5E497161BCC8A198F,
"x":1,
"y":0x3FA8124359F96680B83D1C3EB2C070E5C545C9858D03ECFB744BF8D717717EFC,
"n":32
},
{
"OID":"id-GostR3410-2001-CryptoPro-C-ParamSet",
"p":0x9B9F605F5A858107AB1EC85E6B41C8AACF846E86789051D37998F7B9022D759B,
"a":0x9B9F605F5A858107AB1EC85E6B41C8AACF846E86789051D37998F7B9022D7598,
"b":32858,
"m":0x9B9F605F5A858107AB1EC85E6B41C8AA582CA3511EDDFB74F02F3A6598980BB9,
"q":0x9B9F605F5A858107AB1EC85E6B41C8AA582CA3511EDDFB74F02F3A6598980BB9,
"x":0,
"y":0x41ECE55743711A8C3CBF3783CD08C0EE4D4DC440D4641A8F366E550DFDB3BB67,
"n":32
},

{
"OID":"id-tc26-gost-3410-2012-512-paramSetA",
"p":(0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFL<<296)+\
    (0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFL<<80)+\
    0xFFFFFFFFFFFFFFFFFDC7L,
"a":(0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFL<<296)+\
    (0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFL<<80)+\
    0xFFFFFFFFFFFFFFFFFDC4L,
"b":(0xE8C2505DEDFC86DDC1BD0B2B6667F1DA34B82574761CB0E879BD08L<<296)+\
    (0x1CFD0B6265EE3CB090F30D27614CB4574010DA90DD862EF9D4EBEEL<<80)+\
    0x4761503190785A71C760L,
"m":(0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFL<<296)+\
    (0xFFFFFFFFFF27E69532F48D89116FF22B8D4E0560609B4B38ABFAD2L<<80)+\
    0xB85DCACDB1411F10B275L,
"q":(0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFL<<296)+\
    (0xFFFFFFFFFF27E69532F48D89116FF22B8D4E0560609B4B38ABFAD2L<<80)+\
    0xB85DCACDB1411F10B275L,
"x":3,
"y":(0x7503CFE87A836AE3A61B8816E25450E6CE5E1C93ACF1ABC1778064L<<296)+\
    (0xFDCBEFA921DF1626BE4FD036E93D75E6A50E3A41E98028FE5FC235L<<80)+\
    0xF5B889A589CB5215F2A4L,
"n":64
},
{
"OID":"id-tc26-gost-3410-2012-512-paramSetB",
"p":(0x800000000000000000000000000000000000000000000000000000L<<296)+\
    (0x000000000000000000000000000000000000000000000000000000L<<80)+\
    0x0000000000000000006FL,
"a":(0x800000000000000000000000000000000000000000000000000000L<<296)+\
    (0x000000000000000000000000000000000000000000000000000000L<<80)+\
    0x0000000000000000006CL,
"b":(0x687D1B459DC841457E3E06CF6F5E2517B97C7D614AF138BCBF85DCL<<296)+\
    (0x806C4B289F3E965D2DB1416D217F8B276FAD1AB69C50F78BEE1FA3L<<80)+\
    0x106EFB8CCBC7C5140116L,
"m":(0x800000000000000000000000000000000000000000000000000000L<<296)+\
    (0x000000000149A1EC142565A545ACFDB77BD9D40CFA8B996712101BL<<80)+\
    0xEA0EC6346C54374F25BDL,
"q":(0x800000000000000000000000000000000000000000000000000000L<<296)+\
    (0x000000000149A1EC142565A545ACFDB77BD9D40CFA8B996712101BL<<80)+\
    0xEA0EC6346C54374F25BDL,
"x":2,
"y":(0x1A8F7EDA389B094C2C071E3647A8940F3C123B697578C213BE6DD9L<<296)+\
    (0xE6C8EC7335DCB228FD1EDF4A39152CBCAAF8C0398828041055F94CL<<80)+\
    0xEEEC7E21340780FE41BDL,
"n":64
},

{
"OID":"id-tc26-gost-3410-2012-256-paramSetA",
"p":0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFD97,
"a":0xC2173F1513981673AF4892C23035A27CE25E2013BF95AA33B22C656F277E7335,
"b":0x295F9BAE7428ED9CCC20E7C359A9D41A22FCCD9108E17BF7BA9337A6F8AE9513,
"m":0x1000000000000000000000000000000003F63377F21ED98D70456BD55B0D8319C,
"q":0x400000000000000000000000000000000FD8CDDFC87B6635C115AF556C360C67,
"x":0x91E38443A5E82C0D880923425712B2BB658B9196932E02C78B2582FE742DAA28,
"y":0x32879423AB1A0375895786C4BB46E9565FDE0B5344766740AF268ADB32322E5C,
"n":32
},
{
"OID":"id-tc26-gost-3410-2012-512-paramSetC",
"p":(0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFL<<296)+\
    (0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFL<<80)+\
    0xFFFFFFFFFFFFFFFFFDC7L,
"a":(0xDC9203E514A721875485A529D2C722FB187BC8980EB866644DE41CL<<296)+\
    (0x68E143064546E861C0E2C9EDD92ADE71F46FCF50FF2AD97F951FDAL<<80)+\
    0x9F2A2EB6546F39689BD3L,
"b":(0xB4C4EE28CEBC6C2C8AC12952CF37F16AC7EFB6A9F69F4B57FFDA2EL<<296)+\
    (0x4F0DE5ADE038CBC2FFF719D2C18DE0284B8BFEF3B52B8CC7A5F5BFL<<80)+\
    0x0A3C8D2319A5312557E1L,
"m":(0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFL<<296)+\
    (0xFFFFFFFFFF26336E91941AAC0130CEA7FD451D40B323B6A79E9DA6L<<80)+\
    0x849A5188F3BD1FC08FB4L,
"q":(0x3FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFL<<296)+\
    (0xFFFFFFFFFFC98CDBA46506AB004C33A9FF5147502CC8EDA9E7A769L<<80)+\
    0xA12694623CEF47F023EDL,
"x":(0xE2E31EDFC23DE7BDEBE241CE593EF5DE2295B7A9CBAEF021D385F7L<<296)+\
    (0x074CEA043AA27272A7AE602BF2A7B9033DB9ED3610C6FB85487EAEL<<80)+\
    0x97AAC5BC7928C1950148L,
"y":(0xF5CE40D95B5EB899ABBCCFF5911CB8577939804D6527378B8C108CL<<296)+\
    (0x3D2090FF9BE18E2D33E3021ED2EF32D85822423B6304F726AA854BL<<80)+\
    0xAE07D0396E9A9ADDC40FL,
"n":64
}
]

def str2list( s ):
  res = []
  for c in s:
    res += [ ord( c ) ]
  return res

def list2str( l ):
  r = ""
  for k in l:
    r += chr( k )
  return r

def hprint( data ):
  r = ""
  for i in range( len( data ) ):
    r += "%02X " % data[ i ]
    if i % 16 == 15:
      r += "\n"
  print( r )

class Stribog:

  __A = [
    0x8e20faa72ba0b470, 0x47107ddd9b505a38, 0xad08b0e0c3282d1c,
    0xd8045870ef14980e, 0x6c022c38f90a4c07, 0x3601161cf205268d,
    0x1b8e0b0e798c13c8, 0x83478b07b2468764, 0xa011d380818e8f40,
    0x5086e740ce47c920, 0x2843fd2067adea10, 0x14aff010bdd87508,
    0x0ad97808d06cb404, 0x05e23c0468365a02, 0x8c711e02341b2d01,
    0x46b60f011a83988e, 0x90dab52a387ae76f, 0x486dd4151c3dfdb9,
    0x24b86a840e90f0d2, 0x125c354207487869, 0x092e94218d243cba,
    0x8a174a9ec8121e5d, 0x4585254f64090fa0, 0xaccc9ca9328a8950,
    0x9d4df05d5f661451, 0xc0a878a0a1330aa6, 0x60543c50de970553,
    0x302a1e286fc58ca7, 0x18150f14b9ec46dd, 0x0c84890ad27623e0,
    0x0642ca05693b9f70, 0x0321658cba93c138, 0x86275df09ce8aaa8,
    0x439da0784e745554, 0xafc0503c273aa42a, 0xd960281e9d1d5215,
    0xe230140fc0802984, 0x71180a8960409a42, 0xb60c05ca30204d21,
    0x5b068c651810a89e, 0x456c34887a3805b9, 0xac361a443d1c8cd2,
    0x561b0d22900e4669, 0x2b838811480723ba, 0x9bcf4486248d9f5d,
    0xc3e9224312c8c1a0, 0xeffa11af0964ee50, 0xf97d86d98a327728,
    0xe4fa2054a80b329c, 0x727d102a548b194e, 0x39b008152acb8227,
    0x9258048415eb419d, 0x492c024284fbaec0, 0xaa16012142f35760,
    0x550b8e9e21f7a530, 0xa48b474f9ef5dc18, 0x70a6a56e2440598e,
    0x3853dc371220a247, 0x1ca76e95091051ad, 0x0edd37c48a08a6d8,
    0x07e095624504536c, 0x8d70c431ac02a736, 0xc83862965601dd1b,
    0x641c314b2b8ee083
  ]

  __Sbox = [
    0xFC, 0xEE, 0xDD, 0x11, 0xCF, 0x6E, 0x31, 0x16, 0xFB, 0xC4, 0xFA,
    0xDA, 0x23, 0xC5, 0x04, 0x4D, 0xE9, 0x77, 0xF0, 0xDB, 0x93, 0x2E,
    0x99, 0xBA, 0x17, 0x36, 0xF1, 0xBB, 0x14, 0xCD, 0x5F, 0xC1, 0xF9,
    0x18, 0x65, 0x5A, 0xE2, 0x5C, 0xEF, 0x21, 0x81, 0x1C, 0x3C, 0x42,
    0x8B, 0x01, 0x8E, 0x4F, 0x05, 0x84, 0x02, 0xAE, 0xE3, 0x6A, 0x8F,
    0xA0, 0x06, 0x0B, 0xED, 0x98, 0x7F, 0xD4, 0xD3, 0x1F, 0xEB, 0x34,
    0x2C, 0x51, 0xEA, 0xC8, 0x48, 0xAB, 0xF2, 0x2A, 0x68, 0xA2, 0xFD,
    0x3A, 0xCE, 0xCC, 0xB5, 0x70, 0x0E, 0x56, 0x08, 0x0C, 0x76, 0x12,
    0xBF, 0x72, 0x13, 0x47, 0x9C, 0xB7, 0x5D, 0x87, 0x15, 0xA1, 0x96,
    0x29, 0x10, 0x7B, 0x9A, 0xC7, 0xF3, 0x91, 0x78, 0x6F, 0x9D, 0x9E,
    0xB2, 0xB1, 0x32, 0x75, 0x19, 0x3D, 0xFF, 0x35, 0x8A, 0x7E, 0x6D,
    0x54, 0xC6, 0x80, 0xC3, 0xBD, 0x0D, 0x57, 0xDF, 0xF5, 0x24, 0xA9,
    0x3E, 0xA8, 0x43, 0xC9, 0xD7, 0x79, 0xD6, 0xF6, 0x7C, 0x22, 0xB9,
    0x03, 0xE0, 0x0F, 0xEC, 0xDE, 0x7A, 0x94, 0xB0, 0xBC, 0xDC, 0xE8,
    0x28, 0x50, 0x4E, 0x33, 0x0A, 0x4A, 0xA7, 0x97, 0x60, 0x73, 0x1E,
    0x00, 0x62, 0x44, 0x1A, 0xB8, 0x38, 0x82, 0x64, 0x9F, 0x26, 0x41,
    0xAD, 0x45, 0x46, 0x92, 0x27, 0x5E, 0x55, 0x2F, 0x8C, 0xA3, 0xA5,
    0x7D, 0x69, 0xD5, 0x95, 0x3B, 0x07, 0x58, 0xB3, 0x40, 0x86, 0xAC,
    0x1D, 0xF7, 0x30, 0x37, 0x6B, 0xE4, 0x88, 0xD9, 0xE7, 0x89, 0xE1,
    0x1B, 0x83, 0x49, 0x4C, 0x3F, 0xF8, 0xFE, 0x8D, 0x53, 0xAA, 0x90,
    0xCA, 0xD8, 0x85, 0x61, 0x20, 0x71, 0x67, 0xA4, 0x2D, 0x2B, 0x09,
    0x5B, 0xCB, 0x9B, 0x25, 0xD0, 0xBE, 0xE5, 0x6C, 0x52, 0x59, 0xA6,
    0x74, 0xD2, 0xE6, 0xF4, 0xB4, 0xC0, 0xD1, 0x66, 0xAF, 0xC2, 0x39,
    0x4B, 0x63, 0xB6
  ]

  __Tau = [
    0,  8, 16, 24, 32, 40, 48, 56,
    1,  9, 17, 25, 33, 41, 49, 57,
    2, 10, 18, 26, 34, 42, 50, 58,
    3, 11, 19, 27, 35, 43, 51, 59,
    4, 12, 20, 28, 36, 44, 52, 60,
    5, 13, 21, 29, 37, 45, 53, 61,
    6, 14, 22, 30, 38, 46, 54, 62,
    7, 15, 23, 31, 39, 47, 55, 63
  ]

  __C = [
    [
      0xb1, 0x08, 0x5b, 0xda, 0x1e, 0xca, 0xda, 0xe9,
      0xeb, 0xcb, 0x2f, 0x81, 0xc0, 0x65, 0x7c, 0x1f,
      0x2f, 0x6a, 0x76, 0x43, 0x2e, 0x45, 0xd0, 0x16,
      0x71, 0x4e, 0xb8, 0x8d, 0x75, 0x85, 0xc4, 0xfc,
      0x4b, 0x7c, 0xe0, 0x91, 0x92, 0x67, 0x69, 0x01,
      0xa2, 0x42, 0x2a, 0x08, 0xa4, 0x60, 0xd3, 0x15,
      0x05, 0x76, 0x74, 0x36, 0xcc, 0x74, 0x4d, 0x23,
      0xdd, 0x80, 0x65, 0x59, 0xf2, 0xa6, 0x45, 0x07
    ],
    [
      0x6f, 0xa3, 0xb5, 0x8a, 0xa9, 0x9d, 0x2f, 0x1a,
      0x4f, 0xe3, 0x9d, 0x46, 0x0f, 0x70, 0xb5, 0xd7,
      0xf3, 0xfe, 0xea, 0x72, 0x0a, 0x23, 0x2b, 0x98,
      0x61, 0xd5, 0x5e, 0x0f, 0x16, 0xb5, 0x01, 0x31,
      0x9a, 0xb5, 0x17, 0x6b, 0x12, 0xd6, 0x99, 0x58,
      0x5c, 0xb5, 0x61, 0xc2, 0xdb, 0x0a, 0xa7, 0xca,
      0x55, 0xdd, 0xa2, 0x1b, 0xd7, 0xcb, 0xcd, 0x56,
      0xe6, 0x79, 0x04, 0x70, 0x21, 0xb1, 0x9b, 0xb7
    ],
    [
      0xf5, 0x74, 0xdc, 0xac, 0x2b, 0xce, 0x2f, 0xc7,
      0x0a, 0x39, 0xfc, 0x28, 0x6a, 0x3d, 0x84, 0x35,
      0x06, 0xf1, 0x5e, 0x5f, 0x52, 0x9c, 0x1f, 0x8b,
      0xf2, 0xea, 0x75, 0x14, 0xb1, 0x29, 0x7b, 0x7b,
      0xd3, 0xe2, 0x0f, 0xe4, 0x90, 0x35, 0x9e, 0xb1,
      0xc1, 0xc9, 0x3a, 0x37, 0x60, 0x62, 0xdb, 0x09,
      0xc2, 0xb6, 0xf4, 0x43, 0x86, 0x7a, 0xdb, 0x31,
      0x99, 0x1e, 0x96, 0xf5, 0x0a, 0xba, 0x0a, 0xb2
    ],
    [
      0xef, 0x1f, 0xdf, 0xb3, 0xe8, 0x15, 0x66, 0xd2,
      0xf9, 0x48, 0xe1, 0xa0, 0x5d, 0x71, 0xe4, 0xdd,
      0x48, 0x8e, 0x85, 0x7e, 0x33, 0x5c, 0x3c, 0x7d,
      0x9d, 0x72, 0x1c, 0xad, 0x68, 0x5e, 0x35, 0x3f,
      0xa9, 0xd7, 0x2c, 0x82, 0xed, 0x03, 0xd6, 0x75,
      0xd8, 0xb7, 0x13, 0x33, 0x93, 0x52, 0x03, 0xbe,
      0x34, 0x53, 0xea, 0xa1, 0x93, 0xe8, 0x37, 0xf1,
      0x22, 0x0c, 0xbe, 0xbc, 0x84, 0xe3, 0xd1, 0x2e
    ],

    [
      0x4b, 0xea, 0x6b, 0xac, 0xad, 0x47, 0x47, 0x99,
      0x9a, 0x3f, 0x41, 0x0c, 0x6c, 0xa9, 0x23, 0x63,
      0x7f, 0x15, 0x1c, 0x1f, 0x16, 0x86, 0x10, 0x4a,
      0x35, 0x9e, 0x35, 0xd7, 0x80, 0x0f, 0xff, 0xbd,
      0xbf, 0xcd, 0x17, 0x47, 0x25, 0x3a, 0xf5, 0xa3,
      0xdf, 0xff, 0x00, 0xb7, 0x23, 0x27, 0x1a, 0x16,
      0x7a, 0x56, 0xa2, 0x7e, 0xa9, 0xea, 0x63, 0xf5,
      0x60, 0x17, 0x58, 0xfd, 0x7c, 0x6c, 0xfe, 0x57
    ],
    [
      0xae, 0x4f, 0xae, 0xae, 0x1d, 0x3a, 0xd3, 0xd9,
      0x6f, 0xa4, 0xc3, 0x3b, 0x7a, 0x30, 0x39, 0xc0,
      0x2d, 0x66, 0xc4, 0xf9, 0x51, 0x42, 0xa4, 0x6c,
      0x18, 0x7f, 0x9a, 0xb4, 0x9a, 0xf0, 0x8e, 0xc6,
      0xcf, 0xfa, 0xa6, 0xb7, 0x1c, 0x9a, 0xb7, 0xb4,
      0x0a, 0xf2, 0x1f, 0x66, 0xc2, 0xbe, 0xc6, 0xb6,
      0xbf, 0x71, 0xc5, 0x72, 0x36, 0x90, 0x4f, 0x35,
      0xfa, 0x68, 0x40, 0x7a, 0x46, 0x64, 0x7d, 0x6e
    ],
    [
      0xf4, 0xc7, 0x0e, 0x16, 0xee, 0xaa, 0xc5, 0xec,
      0x51, 0xac, 0x86, 0xfe, 0xbf, 0x24, 0x09, 0x54,
      0x39, 0x9e, 0xc6, 0xc7, 0xe6, 0xbf, 0x87, 0xc9,
      0xd3, 0x47, 0x3e, 0x33, 0x19, 0x7a, 0x93, 0xc9,
      0x09, 0x92, 0xab, 0xc5, 0x2d, 0x82, 0x2c, 0x37,
      0x06, 0x47, 0x69, 0x83, 0x28, 0x4a, 0x05, 0x04,
      0x35, 0x17, 0x45, 0x4c, 0xa2, 0x3c, 0x4a, 0xf3,
      0x88, 0x86, 0x56, 0x4d, 0x3a, 0x14, 0xd4, 0x93
    ],
    [
      0x9b, 0x1f, 0x5b, 0x42, 0x4d, 0x93, 0xc9, 0xa7,
      0x03, 0xe7, 0xaa, 0x02, 0x0c, 0x6e, 0x41, 0x41,
      0x4e, 0xb7, 0xf8, 0x71, 0x9c, 0x36, 0xde, 0x1e,
      0x89, 0xb4, 0x44, 0x3b, 0x4d, 0xdb, 0xc4, 0x9a,
      0xf4, 0x89, 0x2b, 0xcb, 0x92, 0x9b, 0x06, 0x90,
      0x69, 0xd1, 0x8d, 0x2b, 0xd1, 0xa5, 0xc4, 0x2f,
      0x36, 0xac, 0xc2, 0x35, 0x59, 0x51, 0xa8, 0xd9,
      0xa4, 0x7f, 0x0d, 0xd4, 0xbf, 0x02, 0xe7, 0x1e
    ],

    [
      0x37, 0x8f, 0x5a, 0x54, 0x16, 0x31, 0x22, 0x9b,
      0x94, 0x4c, 0x9a, 0xd8, 0xec, 0x16, 0x5f, 0xde,
      0x3a, 0x7d, 0x3a, 0x1b, 0x25, 0x89, 0x42, 0x24,
      0x3c, 0xd9, 0x55, 0xb7, 0xe0, 0x0d, 0x09, 0x84,
      0x80, 0x0a, 0x44, 0x0b, 0xdb, 0xb2, 0xce, 0xb1,
      0x7b, 0x2b, 0x8a, 0x9a, 0xa6, 0x07, 0x9c, 0x54,
      0x0e, 0x38, 0xdc, 0x92, 0xcb, 0x1f, 0x2a, 0x60,
      0x72, 0x61, 0x44, 0x51, 0x83, 0x23, 0x5a, 0xdb
    ],
    [
      0xab, 0xbe, 0xde, 0xa6, 0x80, 0x05, 0x6f, 0x52,
      0x38, 0x2a, 0xe5, 0x48, 0xb2, 0xe4, 0xf3, 0xf3,
      0x89, 0x41, 0xe7, 0x1c, 0xff, 0x8a, 0x78, 0xdb,
      0x1f, 0xff, 0xe1, 0x8a, 0x1b, 0x33, 0x61, 0x03,
      0x9f, 0xe7, 0x67, 0x02, 0xaf, 0x69, 0x33, 0x4b,
      0x7a, 0x1e, 0x6c, 0x30, 0x3b, 0x76, 0x52, 0xf4,
      0x36, 0x98, 0xfa, 0xd1, 0x15, 0x3b, 0xb6, 0xc3,
      0x74, 0xb4, 0xc7, 0xfb, 0x98, 0x45, 0x9c, 0xed
    ],
    [
      0x7b, 0xcd, 0x9e, 0xd0, 0xef, 0xc8, 0x89, 0xfb,
      0x30, 0x02, 0xc6, 0xcd, 0x63, 0x5a, 0xfe, 0x94,
      0xd8, 0xfa, 0x6b, 0xbb, 0xeb, 0xab, 0x07, 0x61,
      0x20, 0x01, 0x80, 0x21, 0x14, 0x84, 0x66, 0x79,
      0x8a, 0x1d, 0x71, 0xef, 0xea, 0x48, 0xb9, 0xca,
      0xef, 0xba, 0xcd, 0x1d, 0x7d, 0x47, 0x6e, 0x98,
      0xde, 0xa2, 0x59, 0x4a, 0xc0, 0x6f, 0xd8, 0x5d,
      0x6b, 0xca, 0xa4, 0xcd, 0x81, 0xf3, 0x2d, 0x1b
    ],
    [
      0x37, 0x8e, 0xe7, 0x67, 0xf1, 0x16, 0x31, 0xba,
      0xd2, 0x13, 0x80, 0xb0, 0x04, 0x49, 0xb1, 0x7a,
      0xcd, 0xa4, 0x3c, 0x32, 0xbc, 0xdf, 0x1d, 0x77,
      0xf8, 0x20, 0x12, 0xd4, 0x30, 0x21, 0x9f, 0x9b,
      0x5d, 0x80, 0xef, 0x9d, 0x18, 0x91, 0xcc, 0x86,
      0xe7, 0x1d, 0xa4, 0xaa, 0x88, 0xe1, 0x28, 0x52,
      0xfa, 0xf4, 0x17, 0xd5, 0xd9, 0xb2, 0x1b, 0x99,
      0x48, 0xbc, 0x92, 0x4a, 0xf1, 0x1b, 0xd7, 0x20
    ]
  ]

  def __AddModulo(self, A, B):
    result = [0] * 64
    t = 0
    for i in reversed(range(0, 64)):
      t = A[i] + B[i] + (t >> 8)
      result[i] = t & 0xFF
    return result

  def __AddXor(self, A, B):
    result = [0] * 64
    for i in range(0, 64):
      result[i] = A[i] ^ B[i]
    return result

  def __S(self, state):
    result = [0] * 64
    for i in range(0, 64):
      result[i] = self.__Sbox[state[i]]
    return result

  def __P(self, state):
    result = [0] * 64
    for i in range(0, 64):
      result[i] = state[self.__Tau[i]]
    return result

  def __L(self, state):
    result = [0] * 64
    for i in range(0, 8):
      t = 0
      for k in range(0, 8):
        for j in range(0, 8):
          if ((state[i * 8 + k] & (1 << (7 - j))) != 0):
            t ^= self.__A[k * 8 + j]
      for k in range(0, 8):
        result[i * 8 + k] = (t & (0xFF << (7 - k) * 8)) >> (7 - k) * 8
    return result

  def __KeySchedule(self, K, i):
    K = self.__AddXor(K, self.__C[i])
    K = self.__S(K)
    K = self.__P(K)
    K = self.__L(K)
    return K

  # E(K, m)
  def __E(self, K, m):
    state = self.__AddXor(K, m)
    for i in range(0, 12):
      state = self.__S(state)
      state = self.__P(state)
      state = self.__L(state)
      K = self.__KeySchedule(K, i)
      state = self.__AddXor(state, K)
    return state

  def __G_n(self, N, h, m):
    K = self.__AddXor(h, N)
    K = self.__S(K)
    K = self.__P(K)
    K = self.__L(K)
    t = self.__E(K, m)
    t = self.__AddXor(t, h)
    return self.__AddXor(t, m)

  def __Padding(self, last, N, h, Sigma):
    if (len(last) < 64):
      padding = [0] * (64 - len(last))
      padding[-1] = 1
      padded_message = padding + last
    h = self.__G_n(N, h, padded_message)
    N_len = [0] * 64
    N_len[63] = (len(last) * 8) & 0xff
    N_len[62] = (len(last) * 8) >> 8
    N = self.__AddModulo(N, N_len)
    Sigma = self.__AddModulo(Sigma, padded_message)
    return (h, N, Sigma)

  def digest( self, message, out=512 ):
    return list2str( self.GetHash( str2list( message ), out ) )

  def GetHash(self, message, out=512, no_pad=False):
    N = [0] * 64
    Sigma = [0] * 64
    if out == 512:
      h = [0] * 64
    elif out == 256:
      h = [0x01] * 64
    else:
      print("Wrong hash out length!")

    N_512 = [0] * 64
    N_512[62] = 0x02    # 512 = 0x200

    length_bits = len(message) * 8
    length = len(message)

    i = 0
    asd = message[::-1]
    while (length_bits >= 512):
      tmp = (message[i * 64: (i + 1) * 64])[::-1]
      h = self.__G_n(N, h, tmp)
      N = self.__AddModulo(N, N_512)
      Sigma = self.__AddModulo(Sigma, tmp)
      length_bits -= 512
      i += 1

    last = (message[i * 64: length])[::-1]

    if (len(last) == 0 and no_pad):
      pass
    else:
      h, N, Sigma = self.__Padding(last, N, h, Sigma)

    N_0 = [0] * 64
    h = self.__G_n(N_0, h, N)
    h = self.__G_n(N_0, h, Sigma)

    if out == 512:
      return h[::-1]
    elif out == 256:
      return (h[0:32])[::-1]

  def hash(self, str_message, out=512, no_pad=False):
    return list2str(self.GetHash(str2list(str_message), out, no_pad))

def H256(msg):
  S = Stribog()
  return S.hash(msg, out=256)

def H512(msg):
  S = Stribog()
  return S.hash(msg)

def num2le( s, n ):
  res = ""
  for i in range(n):
    res += chr(s & 0xFF)
    s >>= 8
  return res

def le2num( s ):
  res = 0
  for i in range(len(s) - 1, -1, -1):
    res = (res << 8) + ord(s[i])
  return res

def XGCD(a,b):
  """XGCD(a,b) returns a list of form [g,x,y], where g is GCD(a,b) and
  x,y satisfy the equation g = ax + by."""
  a1=1; b1=0; a2=0; b2=1; aneg=1; bneg=1; swap = False
  if(a < 0):
    a = -a; aneg=-1
  if(b < 0):
    b = -b; bneg=-1
  if(b > a):
    swap = True
    [a,b] = [b,a]
  while (1):
    quot = -(a / b)
    a = a % b
    a1 = a1 + quot*a2; b1 = b1 + quot*b2
    if(a == 0):
      if(swap):
        return [b, b2*bneg, a2*aneg]
      else:
        return [b, a2*aneg, b2*bneg]
    quot = -(b / a)
    b = b % a
    a2 = a2 + quot*a1; b2 = b2 + quot*b1
    if(b == 0):
      if(swap):
        return [a, b1*bneg, a1*aneg]
      else:
        return [a, a1*aneg, b1*bneg]

def getMultByMask( elems, mask ):
  n = len( elems )
  r = 1
  for i in range( n ):
    if mask & 1:
      r *= elems[ n - 1 - i ]
    mask = mask >> 1
  return r

def subF(P, other, p):
  return (P - other) % p

def divF(P, other, p):
  return mulF(P, invF(other, p), p)

def addF(P, other, p):
  return (P + other) % p

def mulF(P, other, p):
  return (P * other) % p

def invF(R, p):
  assert (R != 0)
  return XGCD(R, p)[1] % p

def negF(R, p):
  return (-R) % p

def powF(R, m, p):
  assert R != None
  assert type(m) in (int, long)

  if m == 0:
    assert R != 0
    return 1
  elif m < 0:
    t = invF(R, p)
    return powF(t, (-m), p)
  else:
    i = m.bit_length() - 1
    r = 1
    while i > 0:
      if (m >> i) & 1:
        r = (r * R) % p
      r = (r * r) % p
      i -= 1
    if m & 1:
      r = (r * R) % p
    return r

def add(Px, Py, Qx, Qy, p, a, b):
  if Qx == Qy == None:
    return [Px, Py]

  if Px == Py == None:
    return [Qx, Qy]

  if (Px == Qx) and (Py == negF(Qy, p)):
    return [None, None]

  if (Px == Qx) and (Py == Qy):
    assert Py != 0
    return duplicate(Px, Py, p, a)
  else:
    l = divF( subF( Qy, Py, p ), subF( Qx, Px, p ), p )
    resX = subF( subF( powF( l, 2, p ), Px, p ), Qx, p )
    resY = subF( mulF( l, subF( Px, resX, p ), p ), Py, p )
    return [resX, resY]

def duplicate(Px, Py, p, a):
  if (Px == None) and (Py == None):
    return [None, None]

  if Py == 0:
    return [None, None]

  l = divF(addF(mulF(powF(Px, 2, p), 3, p), a, p), mulF(Py, 2, p), p)
  resX = subF(powF(l, 2, p), mulF(Px, 2, p), p)
  resY = subF(mulF(l, subF(Px, resX, p), p), Py, p)
  return [resX, resY]

def mul(Px, Py, s, p, a, b):
  assert type(s) in (int, long)
  assert Px != None and Py != None

  X = Px
  Y = Py

  i = s.bit_length() - 1
  resX = None
  resY = None
  while i > 0:
    if (s >> i) & 1:
      resX, resY = add(resX, resY, X, Y, p, a, b)
    resX, resY = duplicate(resX, resY, p, a)
    i -= 1
  if s & 1:
    resX, resY = add(resX, resY, X, Y, p, a, b)
  return [resX, resY]

def Ord(Px, Py, m, q, p, a, b):
  assert Px != None and Py != None
  assert (m != None) and (q != None)
  assert mul(Px, Py, m, p, a, b) == [None, None]

  X = Px
  Y = Py
  r = m
  for mask in range(1 << len(q)):
    t = getMultByMask(q, mask)
    Rx, Ry = mul(X, Y, t, p, a, b)
    if (Rx == None) and (Ry == None):
      r = min(r, t)
  return r

def isQuadraticResidue( R, p ):
  if R == 0:
    assert False
  temp = powF(R, ((p - 1) / 2), p)
  if temp == (p - 1):
    return False
  else:
    assert temp == 1
    return True

def getRandomQuadraticNonresidue(p):
  from random import randint
  r = (randint(2, p - 1)) % p
  while isQuadraticResidue(r, p):
    r = (randint(2, p - 1)) % p
  return r

def ModSqrt( R, p ):
  assert R != None
  assert isQuadraticResidue(R, p)

  if p % 4 == 3:
    res = powF(R, (p + 1) / 4, p)
    if powF(res, 2, p) != R:
      res = None
    return [res, negF(res, p)]
  else:
    ainvF = invF(R, p)

    s = p - 1
    alpha = 0
    while (s % 2) == 0:
      alpha += 1
      s = s / 2

    b = powF(getRandomQuadraticNonresidue(p), s, p)
    r = powF(R, (s + 1) / 2, p)

    bj = 1
    for k in range(0, alpha - 1):  # alpha >= 2 because p % 4 = 1
      d = 2 ** (alpha - k - 2)
      x = powF(mulF(powF(mulF(bj, r, p), 2, p), ainvF, p), d, p)
      if x != 1:
        bj = mulF(bj, powF(b, (2 ** k), p), p)
    res = mulF(bj, r, p)
    return [res, negF(res, p)]

def generateQs( p, pByteSize, a, b, m, q, orderDivisors, Px, Py, N ):
  assert pByteSize in ( 256 / 8, 512 / 8 )
  PxBytes = num2le( Px, pByteSize )
  PyBytes = num2le( Py, pByteSize )
  Qs = []
  S = []
  Hash_src = []
  Hash_res = []
  co_factor = m / q

  seed = 0
  while len( Qs ) != N:
    hashSrc = PxBytes + PyBytes + num2le( seed, 4 )
    if pByteSize == ( 256 / 8 ):
      QxBytes = H256( hashSrc )
    else:
      QxBytes = H512( hashSrc )

    Qx = le2num( QxBytes ) % p

    R = addF( addF( powF(Qx, 3, p ), mulF(Qx, a, p), p), b, p )
    if ( R == 0 ) or ( not isQuadraticResidue( R, p ) ):
      seed += 1
      continue

    Qy_sqrt = ModSqrt( R, p )
    Qy = min(Qy_sqrt)
    if co_factor * Ord(Qx, Qy, m, orderDivisors, p, a, b) != m:
      seed += 1
      continue

    Qs += [(Qx, Qy)]
    S += [seed]
    Hash_src += [hashSrc]
    Hash_res += [QxBytes]
    seed += 1

  return Qs, S, Hash_src, Hash_res

if __name__ == "__main__":
  for i, curve in enumerate(curvesParams):
    print "A.1." + str(i+1) + ". Curve " + curve["OID"]
    if "3410-2012-256-paramSetA" in curve["OID"] or \
           "3410-2012-512-paramSetC" in curve["OID"]:
      Q, S, Hash_src, Hash_res = generateQs(curve["p"],\
                              curve["n"],\
                              curve["a"],\
                              curve["b"],\
                              curve["m"],\
                              curve["q"],\
                              [ 2, 2, curve["q"]],\
                              curve["x"],\
                              curve["y"],\
                              1)
    else:
      Q, S, Hash_src, Hash_res = generateQs(curve["p"],\
                              curve["n"],\
                              curve["a"],\
                              curve["b"],\
                              curve["m"],\
                              curve["q"],\
                              [curve["q"]],\
                              curve["x"],\
                              curve["y"],\
                              1)

    j = 1
    for q, s, hash_src, hash_res in zip(Q, S, Hash_src, Hash_res):
      print "Point Q_" + str(j)
      j += 1

      print "X=", hex(q[0])[:-1]
      print "Y=", hex(q[1])[:-1]

      print "SEED=","{0:#0{1}x}".format(s,6)
      print

Acknowledgments

   We thank Lolita Sonina, Georgiy Borodin, Sergey Agafin, and Ekaterina
   Smyshlyaeva for their careful readings and useful comments.

Authors' Addresses

   Stanislav Smyshlyaev (editor)
   CRYPTO-PRO
   18, Suschevsky val
   Moscow  127018
   Russian Federation

   Phone: +7 (495) 995-48-20
   Email: svs@cryptopro.ru


   Evgeny Alekseev
   CRYPTO-PRO
   18, Suschevsky val
   Moscow  127018
   Russian Federation

   Phone: +7 (495) 995-48-20
   Email: alekseev@cryptopro.ru


   Igor Oshkin
   CRYPTO-PRO
   18, Suschevsky val
   Moscow  127018
   Russian Federation

   Phone: +7 (495) 995-48-20
   Email: oshkin@cryptopro.ru


   Vladimir Popov
   CRYPTO-PRO
   18, Suschevsky val
   Moscow  127018
   Russian Federation

   Phone: +7 (495) 995-48-20
   Email: vpopov@cryptopro.ru