diff options
| -rw-r--r-- | doc/credits.txt | 6 | ||||
| -rw-r--r-- | doc/license.txt | 2 | ||||
| -rw-r--r-- | include/numthry.h | 10 | ||||
| -rw-r--r-- | src/ressol.cpp | 82 |
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 D: x86/amd64 assembler, BigInt optimizations, Win32 mutex module S: Italy + +N: Falko Strenzke +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; + } + +} |