From 21bebf11a3ad3a271f18222e42de3a3d0901a03f Mon Sep 17 00:00:00 2001
From: mdw <mdw>
Date: Thu, 1 Apr 2004 12:50:41 +0000
Subject: [PATCH] Various bugs and fixes.  Add abstract group testing.

---
 tests/group     | 284 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 tests/mp        |   5 +-
 tests/mpbarrett |  13 ++-
 tests/mpmont    |  13 ++-
 tests/mpx       |   6 +-
 5 files changed, 317 insertions(+), 4 deletions(-)
 create mode 100644 tests/group

diff --git a/tests/group b/tests/group
new file mode 100644
index 0000000..eb9c1fa
--- /dev/null
+++ b/tests/group
@@ -0,0 +1,284 @@
+# $Id: group,v 1.1 2004/04/01 12:50:41 mdw Exp $
+#
+# Test group abstraction, and a bunch of other things.
+
+check {
+  "prime { 29, 7, 16 }" "ok";
+  "prime { 29, 6, 5 }" "not a subgroup";
+  "prime { 21, 2, 2 }" "p is not prime";
+  "prime { 29, 14, 9 }" "group order not prime";        
+
+  "ec { secp224r1 }" "ok";
+
+  "prime { catacomb-g1024 }" "ok";
+
+  "ec { 
+     prime:
+       0xdb7c2abf62e35e668076bead208b
+     primeproj: 
+       0xdb7c2abf62e35e668076bead2088, 0x659ef8ba043916eede8911702b22
+     0x09487239995a5ee76b55f9c2f098, 0xa89ce5af8724c0a23e0e0ff77500
+     0xdb7c2abf62e35e7628dfac6561c5 * 1
+  }" "ok";
+        
+  "ec { 
+     prime:
+       0xdb7c2abf62e35e668076bead208b
+     primeproj: 
+       0xdb7c2abf62e35e668076bead2088, 0x659ef8ba043916eede8911702b22
+       0x09487239995a5ee76b55f9c2f098, 0xa89ce5af8724c0a23e0e0ff77500
+       0xdb7c2abf62e35e7628dfac6561c5 * 2
+  }" "incorrect cofactor";
+
+  # --- This one's oakley-155 ---
+
+  "ec { 
+    binpoly: 0x0800000000000000000000004000000000000001
+    binproj: 0, 0x7338F
+    0xaa089ae4666a422e714651ad9372213fa65a93,
+      0x12d29c630dda76010397809a6816be6d2ffa815
+    0xaaaaaaaaaaaaaaaaaab1fcf1e206f421a3ea1b * 12
+  }" "cofactor out of range";
+
+}
+
+checkelt {
+  "prime { 29, 7, 16 }" 16 0;
+  "prime { 29, 7, 16 }" 2 -1;
+
+  "ec { secp112r1 } "
+    "0x09487239995a5ee76b55f9c2f098, 0xa89ce5af8724c0a23e0e0ff77500"
+    0;
+
+  "ec { 
+    binpoly: 0x0800000000000000000000004000000000000001
+    binproj: 0, 0x7338F
+    0xaa089ae4666a422e714651ad9372213fa65a93,
+      0x12d29c630dda76010397809a6816be6d2ffa815
+    0xaaaaaaaaaaaaaaaaaab1fcf1e206f421a3ea1b * 12
+  }"
+  "0x7b, 0x1c8"
+  -1;
+
+}
+
+mul {
+  "prime { 29, 7, 16 }" 8 7 27;
+
+  "prime { catacomb-g512 }"
+    3344609493517948819439808013094817124423784439045485500527919676470975342917009634212031124646834193243018749323077268170586751415510015906107400678608590
+    32459289443738057373904596685867555624839649360339363831766212033645755638497600605981483758068704145575847399920657057013890131443911836862688141735006
+    1926426135381827210395257472845875618319108487720857260583372274154852182951667715700282388176779441854588992736540698662997833538400244234146123792411051;
+
+  "ec { nist-p192 }"
+    "0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012,
+       0x07192b95ffc8da78631011ed6b24cdd573f977a11e794811"
+    "0xdafebf5828783f2ad35534631588a3f629a70fb16982a888,
+       0xdd6bda0d993da0fa46b27bbc141b868f59331afa5c7e93ab"
+    "0x76e32a2557599e6edcd283201fb2b9aadfd0d359cbb263da,
+       0x782c37e372ba4520aa62e0fed121d49ef3b543660cfd05fd"; 
+}
+
+sqr {
+  "prime { 29, 7, 16 }" 8 6;
+
+  "prime { catacomb-g512 }"
+    3344609493517948819439808013094817124423784439045485500527919676470975342917009634212031124646834193243018749323077268170586751415510015906107400678608590
+    4005285938812802884869056091732317348251189092239718246050415417461526884090403819686629744110427371766834314349639104763417430078158218519967583957470490;
+
+  "ec { nist-p192 }"
+    "0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012,
+       0x07192b95ffc8da78631011ed6b24cdd573f977a11e794811"
+    "0xdafebf5828783f2ad35534631588a3f629a70fb16982a888,
+       0xdd6bda0d993da0fa46b27bbc141b868f59331afa5c7e93ab";    
+}
+
+inv {
+  "prime { 29, 7, 16 }" 9 13;
+  
+  "prime { catacomb-g512 }"
+    3344609493517948819439808013094817124423784439045485500527919676470975342917009634212031124646834193243018749323077268170586751415510015906107400678608590
+    4681416433015777166273237967077695060929667390767517698895765893629657943327105422863170288075976922965513789634412273770969873436435698540384711636714478;
+
+  "ec { nist-p192 }"
+    "0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012,
+       0x07192b95ffc8da78631011ed6b24cdd573f977a11e794811"
+    "0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012,
+       0xf8e6d46a003725879cefee1294db32298c06885ee186b7ee";      
+}
+
+div {
+  "prime { 29, 7, 16 }" 9 5 25;
+
+  "prime { catacomb-g512 }"
+    3344609493517948819439808013094817124423784439045485500527919676470975342917009634212031124646834193243018749323077268170586751415510015906107400678608590
+    1926426135381827210395257472845875618319108487720857260583372274154852182951667715700282388176779441854588992736540698662997833538400244234146123792411051
+    4352638698811548340197747445538844858722300429607827242718336069934302793791666196485760252202755936738278388907467170248315316920551773058188278017435713;
+
+  "ec { nist-p192 }"
+    "0x76e32a2557599e6edcd283201fb2b9aadfd0d359cbb263da,
+       0x782c37e372ba4520aa62e0fed121d49ef3b543660cfd05fd"
+     "0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012,
+       0x07192b95ffc8da78631011ed6b24cdd573f977a11e794811"
+    "0xdafebf5828783f2ad35534631588a3f629a70fb16982a888,
+       0xdd6bda0d993da0fa46b27bbc141b868f59331afa5c7e93ab";
+}
+
+exp {
+  "prime { 29, 7, 16 }" 3 12 16;
+
+  "prime { 29, 7, 16 }" 3 -12 20;
+
+  "prime { catacomb-g512 }"
+    3344609493517948819439808013094817124423784439045485500527919676470975342917009634212031124646834193243018749323077268170586751415510015906107400678608590
+    147362842169670001895012880214773009850
+    2724858367444359999445242030177839616322236716074995568862882751673310120217819866527178352161554441906932468828696070184371718373894212895486594604883052;
+
+  "prime { catacomb-g512 }"
+    3344609493517948819439808013094817124423784439045485500527919676470975342917009634212031124646834193243018749323077268170586751415510015906107400678608590
+    -147362842169670001895012880214773009850
+    1787060841912191849220487080420238350817474901097656088582267726968757275201342587344406900935515285588366012828182975089444331616359162696826008378664956;
+
+  "ec { nist-p192 }"
+    "0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012,
+      0x07192b95ffc8da78631011ed6b24cdd573f977a11e794811"
+    6277101735386680763835789423176059013767194773182842284081
+    inf;
+
+  "ec { nist-p192 }"
+    "0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012,
+      0x07192b95ffc8da78631011ed6b24cdd573f977a11e794811"
+    3131675836296406071791252329528905062261497366991742517193
+    "0x7f55059a125dd0d2b40dc3a712248b2848a5e5fa11111f71,
+      0xc6e91094cb34131e539c3db25f7f32670ef8dfe03a88b6fb";
+
+  "ec { nist-p192 }"
+    "0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012,
+      0x07192b95ffc8da78631011ed6b24cdd573f977a11e794811"
+    3131675836296406071791252329528905062261497366991742517193
+    "0x7f55059a125dd0d2b40dc3a712248b2848a5e5fa11111f71,
+      0xc6e91094cb34131e539c3db25f7f32670ef8dfe03a88b6fb";
+
+  "ec { nist-p192 }"
+    "0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012,
+      0x07192b95ffc8da78631011ed6b24cdd573f977a11e794811"
+    -3131675836296406071791252329528905062261497366991742517193
+    "0x7f55059a125dd0d2b40dc3a712248b2848a5e5fa11111f71,
+      0x3916ef6b34cbece1ac63c24da080cd97f107201fc5774904";
+}
+
+mexp-1 {
+  "prime { 29, 7, 16 }" 3 12 16;
+  "prime { 29, 7, 16 }" 3 -12 20;
+
+  "ec { nist-p192 }"
+    "0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012,
+      0x07192b95ffc8da78631011ed6b24cdd573f977a11e794811"
+    3131675836296406071791252329528905062261497366991742517193
+    "0x7f55059a125dd0d2b40dc3a712248b2848a5e5fa11111f71,
+      0xc6e91094cb34131e539c3db25f7f32670ef8dfe03a88b6fb";
+
+  "ec { nist-p192 }"
+    "0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012,
+      0x07192b95ffc8da78631011ed6b24cdd573f977a11e794811"
+    -3131675836296406071791252329528905062261497366991742517193
+    "0x7f55059a125dd0d2b40dc3a712248b2848a5e5fa11111f71,
+      0x3916ef6b34cbece1ac63c24da080cd97f107201fc5774904";
+}
+
+mexp-2 {
+  "prime { 29, 7, 16 }" 3 12 8 2 9;
+  "prime { 29, 7, 16 }" 3 -12 8 2 4;
+
+  "prime { catacomb-g512 }"
+   3344609493517948819439808013094817124423784439045485500527919676470975342917009634212031124646834193243018749323077268170586751415510015906107400678608590
+   -147362842169670001895012880214773009850
+   130340428707563070626027539288099297037336608388990593367322442443880297841210613523501678207607756678300142264348927299637006055881968995671289567513600
+   91626412351157168611316239052073981423
+   1964042259347008051177500376636104488225042199152152977412099367647894431543835858678217073603604876847502133350210611462670145543437496436961938287223663;
+
+  "ec { nist-p192 }"
+    "0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012,
+      0x07192b95ffc8da78631011ed6b24cdd573f977a11e794811"
+    -3131675836296406071791252329528905062261497366991742517193
+    "0xea711858c23d92f9964655910bc90a197a915e90111cf11b, 
+      0x664189a1d8b2bb24f2b2ac64b19e2178118842e6ba9f4ad5"
+    1110875761630725856340142297645383444629395595869672555585
+    "0xaa25bb0bf38b06821e8641c1afb8bc078dbe11c3cf9bc97,
+       0xf1a4c09d621fb52736f6010ae90e9bc9771ac017a62098f9";
+}
+
+toint {
+  "prime { 29, 7, 16 }" 15 0 15;
+  "prime { 29, 7, 16 }" 0 0 0;
+
+  "ec { nist-p192 }" inf -1 0;
+
+  "ec { nist-p192 }" 
+    "0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012,
+      0x07192b95ffc8da78631011ed6b24cdd573f977a11e794811"
+    0 602046282375688656758213480587526111916698976636884684818;
+}
+
+fromint {
+  "prime { 29, 7, 16 }" 15 0 15;
+  "prime { 29, 7, 16 }" 0 0 0;
+  "prime { 29, 7, 16 }" 39527306161272833161358334459 0 19;
+
+  "ec { nist-p192 }" 1 -1 inf;
+  "ec { nist-p192 }" 0 
+    0 "0, 0x8497a9fa119ff34c9c24a156ed0d44a0c5f5d1f19fc9f0ed";
+}
+
+toec {
+  "prime { 29, 7, 16 }" 0 -1 inf;
+  "ec { nist-p192 }" inf 0 inf;
+  "ec { secp112r1 }" 
+    "0x09487239995a5ee76b55f9c2f098, 0xa89ce5af8724c0a23e0e0ff77500"
+    0
+    "0x09487239995a5ee76b55f9c2f098, 0xa89ce5af8724c0a23e0e0ff77500";
+}
+
+fromec {
+  "prime { 29, 7, 16 }" inf -1 0;
+  "prime { 29, 7, 16 }" "39527306161272833161358334459, 9" 0 19;
+
+  "ec { secp112r1 }" inf 0 inf;
+  "ec { nist-p192 }" "1, 5" -1 inf;
+
+  "ec { secp112r1 }" 
+    "0x09487239995a5ee76b55f9c2f098, 0xa89ce5af8724c0a23e0e0ff77500"
+    0
+    "0x09487239995a5ee76b55f9c2f098, 0xa89ce5af8724c0a23e0e0ff77500";
+}
+
+tobuf {
+  "prime { 29, 7, 16}" 22 -1 "00";
+  "prime { 29, 7, 16}" 22 0 "000116";
+  "prime { 29, 7, 16}" 0 -1 "0000";
+  "prime { 29, 7, 16}" 0 0 "000100";
+
+  "ec { secp112r1 }" inf 0 "0000";
+  "ec { secp112r1 }"
+    "0x09487239995a5ee76b55f9c2f098, 0xa89ce5af8724c0a23e0e0ff77500"
+    0 "000e09487239995a5ee76b55f9c2f098000ea89ce5af8724c0a23e0e0ff77500";      
+  "ec { nist-p192 }"
+    "0, 0x8497a9fa119ff34c9c24a156ed0d44a0c5f5d1f19fc9f0ed"
+    0 "00010000188497a9fa119ff34c9c24a156ed0d44a0c5f5d1f19fc9f0ed";
+}
+
+frombuf {
+  "prime { 29, 7, 16}" "00" -1 0;
+  "prime { 29, 7, 16}" "000116" 3 22;
+  "prime { 29, 7, 16}" "00000e" 2 0;
+  "prime { 29, 7, 16}" "000100ff" 3 0;
+
+  "ec { secp112r1 }" "0000" 2 inf;
+  "ec { secp112r1 }"
+    "000e09487239995a5ee76b55f9c2f098000ea89ce5af8724c0a23e0e0ff77500f00d"
+    32 "0x09487239995a5ee76b55f9c2f098, 0xa89ce5af8724c0a23e0e0ff77500";
+  "ec { secp112r1 }" "0001000001001ee7" -1 inf;
+  "ec { nist-p192 }"
+    "00010000188497a9fa119ff34c9c24a156ed0d44a0c5f5d1f19fc9f0eddead"
+    29, "0, 0x8497a9fa119ff34c9c24a156ed0d44a0c5f5d1f19fc9f0ed";
+}
diff --git a/tests/mp b/tests/mp
index f66795e..34f16f8 100644
--- a/tests/mp
+++ b/tests/mp
@@ -1,6 +1,6 @@
 # Test vectors for MP functions
 #
-# $Id: mp,v 1.16 2003/10/12 15:03:35 mdw Exp $
+# $Id: mp,v 1.17 2004/04/01 12:50:41 mdw Exp $
 
 add {
   5 4 9; 5 -4 1; -5 4 -1; -5 -4 -9;
@@ -27,6 +27,9 @@ div {
   3131675836296406071791252329528905062261497366991742517193
     53
     59088223326347284373419855274130284193613157867768726739 26;
+  1552518092300708935130918131258481755631334049434514313202351194902966239949102107258669453876591642442910007680288864229150803718918046342632727613031282983744380820890196288509170691316593175367469551763119843371637221007210577919
+  776259046150354467565459065629240877815667024717257156601175597451483119974551053629334726938295821221455003840144432114575401859459023171316363806515641491872190410445098144254585345658296587683734775881559921685818610503605288959
+  2 1;
 }
 
 bin2c {
diff --git a/tests/mpbarrett b/tests/mpbarrett
index 4ee624b..c3074d0 100644
--- a/tests/mpbarrett
+++ b/tests/mpbarrett
@@ -1,6 +1,6 @@
 # Test vectors for Barrett modular reduction
 #
-# $Id: mpbarrett,v 1.3 2001/06/16 13:01:25 mdw Exp $
+# $Id: mpbarrett,v 1.4 2004/04/01 12:50:41 mdw Exp $
 
 mpbarrett-reduce {
   17 11 6;
@@ -52,6 +52,10 @@ mpbarrett-exp {
   8939489893434234331 1804289383 454353454354565 6139425926295484741;
   8939489893434234331 1804289383 8939489893434234330 1;
 
+  # --- Negative exponents ---
+
+  8939489893434234331 1804289383 -8939035539979879765 6139425926295484741;
+
   # --- DSA public key derivation ---
 
   0xc9c7feaeaedb16505389c5582df1858d0fdb3eecfe61c230d612661bef8c1bc5
@@ -110,4 +114,11 @@ mexp-2 {
   0x19131871d75b1612a819f29d78d1b0d7346f7aa77bb62a859bfd6c5675da9d212d3a36ef1672ef660b8c7c255cc0ec74858fba33f44c06699630a76b030ee333
   0x821a926312e97adeabcc8d082b5278978a2df4b0
   0x2fc6cb9ac3be0eac3daf02eefb96fca3846708a28dd05730165fe50942f7f07edfef8e52fcb9369e3814aa24607e80475d0e61ad461d6b16b6cec5baae58946e;
+
+  0x8df2a494492276aa3d25759bb06869cbeac0d83afb8d0cf7cbb8324f0d7882e5d0762fc5b7210eafc2e9adac32ab7aac49693dfbf83724c2ec0736ee31c80291
+  0x626d027839ea0a13413163a55b4cb500299d5522956cefcb3bff10f399ce2c2e71cb9de5fa24babf58e5b79521925c9cc42e9f6f464b088cc572af53e6d78802
+  0xbf655bd046f0b35ec791b004804afcbb8ef7d69d
+  0x19131871d75b1612a819f29d78d1b0d7346f7aa77bb62a859bfd6c5675da9d212d3a36ef1672ef660b8c7c255cc0ec74858fba33f44c06699630a76b030ee333
+  -0x8df2a494492276aa3d25759bb06869cbeac0d83afb8d0cf7cbb8324f0d7882e5d0762fc5b7210eafc2e9adabb090e849367fc31d4c6a97bac0b4be56a79a0de0
+  0x2fc6cb9ac3be0eac3daf02eefb96fca3846708a28dd05730165fe50942f7f07edfef8e52fcb9369e3814aa24607e80475d0e61ad461d6b16b6cec5baae58946e;
 }
diff --git a/tests/mpmont b/tests/mpmont
index d7fc0af..389f2ed 100644
--- a/tests/mpmont
+++ b/tests/mpmont
@@ -1,6 +1,6 @@
 # Test vectors for Montgomery reduction
 #
-# $Id: mpmont,v 1.6 2002/01/13 13:43:20 mdw Exp $
+# $Id: mpmont,v 1.7 2004/04/01 12:50:41 mdw Exp $
 
 create {
   340809809850981098423498794792349	# m
@@ -35,6 +35,10 @@ exp {
   8939489893434234331 1804289383 454353454354565 6139425926295484741;
   8939489893434234331 1804289383 8939489893434234330 1;
 
+  # --- Negative exponents ---
+
+  8939489893434234331 1804289383 -8939035539979879765 6139425926295484741;
+
   # --- DSA public key derivation ---
 
   0xc9c7feaeaedb16505389c5582df1858d0fdb3eecfe61c230d612661bef8c1bc5
@@ -100,4 +104,11 @@ mexp-2 {
   0x19131871d75b1612a819f29d78d1b0d7346f7aa77bb62a859bfd6c5675da9d212d3a36ef1672ef660b8c7c255cc0ec74858fba33f44c06699630a76b030ee333
   0x821a926312e97adeabcc8d082b5278978a2df4b0
   0x2fc6cb9ac3be0eac3daf02eefb96fca3846708a28dd05730165fe50942f7f07edfef8e52fcb9369e3814aa24607e80475d0e61ad461d6b16b6cec5baae58946e;
+
+  0x8df2a494492276aa3d25759bb06869cbeac0d83afb8d0cf7cbb8324f0d7882e5d0762fc5b7210eafc2e9adac32ab7aac49693dfbf83724c2ec0736ee31c80291
+  0x626d027839ea0a13413163a55b4cb500299d5522956cefcb3bff10f399ce2c2e71cb9de5fa24babf58e5b79521925c9cc42e9f6f464b088cc572af53e6d78802
+  0xbf655bd046f0b35ec791b004804afcbb8ef7d69d
+  0x19131871d75b1612a819f29d78d1b0d7346f7aa77bb62a859bfd6c5675da9d212d3a36ef1672ef660b8c7c255cc0ec74858fba33f44c06699630a76b030ee333
+  -0x8df2a494492276aa3d25759bb06869cbeac0d83afb8d0cf7cbb8324f0d7882e5d0762fc5b7210eafc2e9adabb090e849367fc31d4c6a97bac0b4be56a79a0de0
+  0x2fc6cb9ac3be0eac3daf02eefb96fca3846708a28dd05730165fe50942f7f07edfef8e52fcb9369e3814aa24607e80475d0e61ad461d6b16b6cec5baae58946e;
 }
diff --git a/tests/mpx b/tests/mpx
index e54af08..7f6ff5e 100644
--- a/tests/mpx
+++ b/tests/mpx
@@ -1,6 +1,6 @@
 # Test vectors for low-level MP functions
 #
-# $Id: mpx,v 1.11 2003/05/16 09:09:24 mdw Exp $
+# $Id: mpx,v 1.12 2004/04/01 12:50:41 mdw Exp $
 
 # --- Load-store tests ---
 #
@@ -881,4 +881,8 @@ udiv {
   184f03e93ff9f4daa797ed6e38ed64bf6a1f010000000000000000
   0117d3db34ad005954459be9abedd0e5deb4ea0000000000000000
   00;
+
+  ffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec6f44c42e9a63a3620ffffffffffffffff
+  7fffffffffffffffe487ed5110b4611a62633145c06e0e68948127044533e63a0105df531d89cd9128a5043cc71a026ef7ca8cd9e69d218d98158536f92f8a1ba7f09ab6b6a8e122f242dabb312f3f637a262174d31d1b107fffffffffffffff
+  02 01;
 }
-- 
2.11.0