Add an implementation of the Shanks-Tonelli algorithm, which is used to

find square roots modulo a prime. Contributed by FlexSecure GmbH

4 files changed, 98 insertions, 2 deletions

diff --git a/doc/credits.txt b/doc/credits.txt
index 57c33b72b..79818565e 100644
--- a/doc/credits.txt
+++ b/doc/credits.txt
@@ -48,3 +48,9 @@ N: Luca Piccarreta
 E: [email protected]
 D: x86/amd64 assembler, BigInt optimizations, Win32 mutex module
 S: Italy
+
+N: Falko Strenzke
+E: [email protected]
+W: http://www.flexsecure.de/
+D: Shanks-Tonelli algorithm
+S: Darmstadt, Germany
diff --git a/doc/license.txt b/doc/license.txt
index 827bc839b..c0fb58c10 100644
--- a/doc/license.txt
+++ b/doc/license.txt
@@ -5,6 +5,8 @@ Copyright (C) 1999-2008 Jack Lloyd
               2005-2006 Matt Johnston
               2006 Luca Piccarreta
               2007 Yves Jerschow
+              2007-2008 FlexSecure GmbH
+              2007-2008 Falko Strenzke
 
 Redistribution and use in source and binary forms, for any use, with or without
 modification, is permitted provided that the following conditions are met:
diff --git a/include/numthry.h b/include/numthry.h
index c6313bdb7..371621c2d 100644
--- a/include/numthry.h
+++ b/include/numthry.h
@@ -36,6 +36,12 @@ s32bit BOTAN_DLL jacobi(const BigInt&, const BigInt&);
 BigInt BOTAN_DLL power_mod(const BigInt&, const BigInt&, const BigInt&);
 
 /*************************************************
+* Compute the square root of x modulo a prime    *
+* using the Shanks-Tonnelli algorithm            *
+*************************************************/
+BigInt ressol(const BigInt& x, const BigInt& p);
+
+/*************************************************
 * Utility Functions                              *
 *************************************************/
 u32bit BOTAN_DLL low_zero_bits(const BigInt&);
@@ -62,8 +68,8 @@ BigInt BOTAN_DLL random_integer(RandomNumberGenerator&,
                                 const BigInt&, const BigInt&);
 
 BigInt BOTAN_DLL random_prime(RandomNumberGenerator&,
-                              u32bit n, const BigInt& = 1,
-                              u32bit = 1, u32bit = 2);
+                              u32bit bits, const BigInt& coprime = 1,
+                              u32bit equiv = 1, u32bit equiv_mod = 2);
 
 BigInt BOTAN_DLL random_safe_prime(RandomNumberGenerator&,
                                    u32bit);
diff --git a/src/ressol.cpp b/src/ressol.cpp
new file mode 100644
index 000000000..e0967eae4
--- /dev/null
+++ b/src/ressol.cpp
@@ -0,0 +1,82 @@
+/*************************************************
+* Shanks-Tonnelli (RESSOL) Source File           *
+* (C) 2007-2008 Falko Strenzke, FlexSecure GmbH  *
+* (C) 2008 Jack Lloyd                            *
+*************************************************/
+
+#include <botan/numthry.h>
+#include <botan/reducer.h>
+
+#include <iostream>
+
+namespace Botan {
+
+/*************************************************
+* Shanks-Tonnelli algorithm                      *
+*************************************************/
+BigInt ressol(const BigInt& a, const BigInt& p)
+   {
+   if(a < 0)
+      throw Invalid_Argument("ressol(): a to solve for must be positive");
+   if(p <= 1)
+      throw Invalid_Argument("ressol(): prime must be > 1");
+
+   if(a == 0)
+      return 0;
+   if(p == 2)
+      return a;
+
+   if(jacobi(a, p) != 1) // not a quadratic residue
+      return -1;
+
+   if(p % 4 == 3)
+      return power_mod(a, ((p+1) >> 2), p);
+
+   u32bit s = low_zero_bits(p - 1);
+   BigInt q = p >> s;
+
+   q -= 1;
+   q >>= 1;
+
+   Modular_Reducer mod_p(p);
+
+   BigInt r = power_mod(a, q, p);
+   BigInt n = mod_p.multiply(a, mod_p.square(r));
+   r = mod_p.multiply(r, a);
+
+   if(n == 1)
+      return r;
+
+   // find random non quadratic residue z
+   BigInt z = 2;
+   while(jacobi(z, p) == 1) // while z quadratic residue
+      ++z;
+
+   BigInt c = power_mod(z, (q << 1) + 1, p);
+
+   while(n > 1)
+      {
+      q = n;
+
+      u32bit i = 0;
+      while(q != 1)
+         {
+         q = mod_p.square(q);
+         ++i;
+         }
+      u32bit t = s;
+
+      if(t <= i)
+         return -1;
+
+      c = power_mod(c, BigInt(BigInt::Power2, t-i-1), p);
+      r = mod_p.multiply(r, c);
+      c = mod_p.square(c);
+      n = mod_p.multiply(n, c);
+      s = i;
+      }
+
+   return r;
+   }
+
+}