The Goldwasser-Kilian Primality proving algorithm was the first method to utilize elliptic curves to generate primality proving certificates. What follows is a file of two certificates and the single precision C source code.
Category: Cryptanalysis
Blog Entry (c) Saturday, August 10, 2024, by James Pate Williams, Jr. The LLL Lattice Reduction Algorithm
Blog Entry Wednesday, July 10, 2024, © James Pate Williams, Jr. My Dual Interests in Cryptography and Number Theory
I became fascinated with secret key cryptography as a child. Later, as an adult, in around 1979, I started creating crude symmetric cryptographic algorithms. I became further enthralled with cryptography and number theory in 1996 upon reading Applied Cryptography, Second Edition: Protocols, Algorithms, and Source Code in C by Bruce Schneier and later the Handbook of Applied Cryptography by Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone. After implementing many of the algorithms in both tomes, I communicated my results to two of the authors namely Bruce Schneier and Professor Alfred J. Menezes. In 1997 I developed a website devoted to constraint satisfaction problems and their solutions, cryptography, and number theory. I posted legal C and C++ source code. Professor Menezes advertised my website along with his treatise. See the following blurb:
In the spirit of my twin scientific infatuations, I offer yet another C integer factoring implementation utilizing the Free Large Integer Package (known more widely as lip) which was created by Arjen K. Lenstra (now a Professor Emeritus). This implementation includes Henri Cohen’s Trial Division algorithm, the Brent-Cohen-Pollard rho method, the Cohen-Pollard p – 1 stage 1 method, and the Lenstra lip Elliptic Curve Method. If I can get the proper authorization, I will later post the source code.
total time required for initialization: 0.056000 seconds
enter number below:
2^111+2
== Menu ==
1 Trial Division
2 Pollard-Brent-Cohen rho
3 p - 1 Pollard-Cohen
4 Lenstra's Elliptic Curve Method
5 Pollard-Lenstra rho
1
2596148429267413814265248164610050
number is composite
factors:
total time required factoring: 0.014000 seconds:
2
5 ^ 2
41
397
2113
enter number below:
0
total time required for initialization: 0.056000 seconds
enter number below:
2^111+2
== Menu ==
1 Trial Division
2 Pollard-Brent-Cohen rho
3 p - 1 Pollard-Cohen
4 Lenstra's Elliptic Curve Method
5 Pollard-Lenstra rho
2
2596148429267413814265248164610050
number is composite
factors:
total time required factoring: 1.531000 seconds:
2
5 ^ 2
41
397
2113
415878438361
3630105520141
enter number below:
0
total time required for initialization: 0.055000 seconds
enter number below:
2^111+2
== Menu ==
1 Trial Division
2 Pollard-Brent-Cohen rho
3 p - 1 Pollard-Cohen
4 Lenstra's Elliptic Curve Method
5 Pollard-Lenstra rho
3
2596148429267413814265248164610050
number is composite
factors:
total time required factoring: 0.066000 seconds:
2
5 ^ 2
41
838861
415878438361
3630105520141
enter number below:
0
total time required for initialization: 0.056000 seconds
enter number below:
2^111+2
== Menu ==
1 Trial Division
2 Pollard-Brent-Cohen rho
3 p - 1 Pollard-Cohen
4 Lenstra's Elliptic Curve Method
5 Pollard-Lenstra rho
4
2596148429267413814265248164610050
number is composite
factors:
total time required factoring: 0.013000 seconds:
2
5
205
838861
415878438361
3630105520141
enter number below:
0
Brute Force Elliptic Curve Point Counting Algorithm Implementation by James Pate Williams, Jr.
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <chrono>
#include <vector>
using namespace std;
typedef long long ll;
typedef struct ecPoint
{
ll x, y;
} ECPOINT, *PECPOINT;
typedef struct ecPointOrder
{
ll order;
ECPOINT pt;
} ECPOINTORDER, * PECPOINTORDER;
int JACOBI(ll a, ll n)
{
int e = 0, s;
ll a1, b = a, m, n1;
if (a == 0) return 0;
if (a == 1) return 1;
while ((b & 1) == 0)
{
b >>= 1;
e++;
}
a1 = b;
m = n % 8;
if (!(e & 1)) s = 1;
else if (m == 1 || m == 7) s = +1;
else if (m == 3 || m == 5) s = -1;
if (n % 4 == 3 && a1 % 4 == 3) s = -s;
if (a1 != 1) n1 = n % a1; else n1 = 1;
return s * JACOBI(n1, a1);
}
ll ExpMod(ll x, ll b, ll n)
/* returns x ^ b mod n */
{
ll a = 1LL, s = x;
if (b == 0)
return 1LL;
while (b != 0) {
if (b & 1l) a = (a * s) % n;
b >>= 1;
if (b != 0) s = (s * s) % n;
}
if (a < 0)
a += n;
return a;
}
ll ExtendedEuclidean(ll b, ll n)
{
ll b0 = b, n0 = n, t = 1, t0 = 0, temp, q, r;
q = n0 / b0;
r = n0 - q * b0;
while (r > 0) {
temp = t0 - q * t;
if (temp >= 0) temp = temp % n;
else temp = n - (-temp % n);
t0 = t;
t = temp;
n0 = b0;
b0 = r;
q = n0 / b0;
r = n0 - q * b0;
}
if (b0 != 1) return 0;
else return t % n;
}
ll Weierstrass(ll a, ll b, ll x, ll p)
{
return ((((x * x) % p) * x) % p + (a * x) % p + b) % p;
}
ll EPoints(
bool print,
ll a, ll b, ll p,
vector<ECPOINT>& e)
/* returns the number of points on the elliptic
curve y ^ 2 = x ^ 3 + ax + b mod p */
{
ll count = 0, m = (p + 1) / 4, x, y;
ECPOINT pt{};
if (p % 4 == 3) {
for (x = 0; x < p; x++) {
y = Weierstrass(a, b, x, p);
if (JACOBI(y, p) != -1) {
y = ExpMod(y, m, p);
if (print)
{
cout << "(" << setw(2) << x << ", ";
cout << y << ") " << endl;
}
pt.x = x;
pt.y = y;
e.push_back(pt);
count++;
y = -y % p;
if (y < 0) y += p;
if (y != 0)
{
if (print)
{
cout << "(" << setw(2) << x << ", ";
cout << y << ") " << endl;
}
pt.x = x;
pt.y = y;
e.push_back(pt);
count++;
}
if (print && count % 5 == 0)
cout << endl;
}
}
if (print && count % 5 != 0)
cout << endl;
}
return count;
}
void Add(ll a, ll p, ECPOINT P,
ECPOINT Q, ECPOINT& R)
/* elliptic curve point partial addition */
{
ll i, lambda;
if (P.x == Q.x && P.y == 0 && Q.y == 0) {
R.x = 0;
R.y = 1;
return;
}
if (P.x == Q.x && P.y == p - Q.y) {
R.x = 0;
R.y = 1;
return;
}
if (P.x == 0 && P.y == 1) {
R = Q;
return;
}
if (Q.x == 0 && Q.y == 1) {
R = P;
return;
}
if (P.x != Q.x) {
i = Q.x - P.x;
if (i < 0) i += p;
i = ExtendedEuclidean(i, p);
lambda = ((Q.y - P.y) * i) % p;
}
else {
i = ExtendedEuclidean((2 * P.y) % p, p);
lambda = ((3 * P.x * P.x + a) * i) % p;
}
if (lambda < 0) lambda += p;
R.x = (lambda * lambda - P.x - Q.x) % p;
R.y = (lambda * (P.x - R.x) - P.y) % p;
if (R.x < 0) R.x += p;
if (R.y < 0) R.y += p;
}
void Multiply(
ll a, ll k, ll p,
ECPOINT P,
ECPOINT& R)
{
ECPOINT S;
R.x = 0;
R.y = 1;
S = P;
while (k != 0) {
if (k & 1) Add(a, p, R, S, R);
k >>= 1;
if (k != 0) Add(a, p, S, S, S);
}
}
ll Order(ll a, ll p, ECPOINT P)
{
ll order = 1;
ECPOINT Q = P, R{};
do {
order++;
Add(a, p, P, Q, R);
Q = R;
} while (R.x != 0 && R.y != 1);
return order;
}
const int PrimeSize = 10000000;
bool sieve[PrimeSize];
void PopulateSieve() {
// sieve of Eratosthenes
int c, inc, i, n = PrimeSize - 1;
for (i = 0; i < n; i++)
sieve[i] = false;
sieve[1] = false;
sieve[2] = true;
for (i = 3; i <= n; i++)
sieve[i] = (i & 1) == 1 ? true : false;
c = 3;
do {
i = c * c;
inc = c + c;
while (i <= n) {
sieve[i] = false;
i += inc;
}
c += 2;
while (!sieve[c])
c++;
} while (c * c <= n);
}
ll Partition(
vector<ECPOINTORDER>& a, ll n, ll lo, ll hi)
{
ll pivotIndex = lo + (hi - lo) / 2;
ECPOINTORDER po = a[(unsigned int)pivotIndex];
ECPOINTORDER x = po;
ECPOINTORDER t = x;
a[(unsigned int)pivotIndex] = a[(unsigned int)hi];
a[(unsigned int)hi] = t;
ll storeIndex = lo;
for (unsigned int i = (unsigned int)lo; i < (unsigned int)hi; i++)
{
if (a[i].order < x.order)
{
t = a[i];
a[i] = a[(unsigned int)storeIndex];
a[(unsigned int)(storeIndex++)] = t;
}
}
t = a[(unsigned int)storeIndex];
a[(unsigned int)storeIndex] = a[(unsigned int)hi];
a[(unsigned int)hi] = t;
return storeIndex;
}
static void DoQuickSort(
vector<ECPOINTORDER>& a, ll n, ll p, ll r)
{
if (p < r)
{
ll q = Partition(a, n, p, r);
DoQuickSort(a, n, p, q - 1);
DoQuickSort(a, n, q + 1, r);
}
}
void QuickSort(vector<ECPOINTORDER>& a, ll n)
{
DoQuickSort(a, n, 0, n - 1);
}
int main()
{
PopulateSieve();
while (true)
{
bool noncyclic = false;
int option;
ll a, b, p;
cout << "Enter 1 to continue or 0 to quit = ";
cin >> option;
if (option == 0)
break;
cout << "Weierstrass parameter a = ";
cin >> a;
cout << "Weierstrass parameter b = ";
cin >> b;
cout << "Enter the prime parameter p = ";
cin >> p;
if (!sieve[p])
{
cout << "p is not a prime number. " << endl;
continue;
}
if (p % 4 != 3)
{
cout << "p mod 4 must be 3 for this algorithm." << endl;
continue;
}
bool print = false, enumerate = false;
vector<ECPOINT> e;
vector<ECPOINTORDER> eOrder;
cout << "Enumerate points (0 for no or 1 for yes)? ";
cin >> option;
enumerate = option == 1;
auto time0 = chrono::high_resolution_clock::now();
ll count = EPoints(print, a, b, p, e);
auto time1 = chrono::high_resolution_clock::now();
auto elapsed = time1 - time0;
ll h = count + 1;
ll maxOrder = 0;
ll minOrder = h;
ll order = -1;
ECPOINT P{}, Q{};
if (enumerate)
cout << "The points (x, y) on E and their orders are:" << endl;
for (unsigned int i = 0; i < count; i++)
{
ECPOINTORDER ptOrder{};
order = Order(a, p, e[i]);
ptOrder.order = order;
ptOrder.pt = e[i];
eOrder.push_back(ptOrder);
if (order < h)
noncyclic = true;
if (order < minOrder) {
P = e[i];
minOrder = order;
}
if (order > maxOrder) {
Q = e[i];
maxOrder = order;
}
}
if (enumerate)
{
QuickSort(eOrder, count);
for (unsigned int i = 0; i < eOrder.size(); i++)
{
cout << "(" << eOrder[i].pt.x << ", ";
cout << eOrder[i].pt.y << ") ";
cout << eOrder[i].order << "\t";
if ((i + 1) % 5 == 0)
cout << endl;
}
if (count % 5 != 0)
cout << endl;
}
cout << "#E = " << h << endl;
cout << "Noncyclic = " << noncyclic << endl;
cout << "Minimum order = " << minOrder << endl;
cout << "Maximum order = " << maxOrder << endl;
cout << "(" << P.x << ", " << P.y << ")" << endl;
cout << "(" << Q.x << ", " << Q.y << ")" << endl;
long long runtime = chrono::duration_cast<chrono::milliseconds>(elapsed).count();
if (runtime != 0)
cout << "Point counting runtime in milliseconds = " << runtime << endl;
else
{
runtime = chrono::duration_cast<chrono::microseconds>(elapsed).count();
cout << "Point counting runtime in microseconds = " << runtime << endl;
}
}
return 0;
}
More Elliptic Curve Point Counting Results Using the Shanks-Mestre Algorithm by James Pate Williams, Jr.
As can be seen the C++ application appears to be much faster than the C# application. Also, in my humble opinion, C++ with header files and C++ source code files is much more elegant than C# with only class source code. I leave it to someone else to add C# interfaces to my class source code files.
Solving the Low-Density Subset Sum Problem with the LLL Lattice Reduction Algorithm C# Implementation by James Pate Williams, Jr.
A few years ago, I implemented the LLL lattice reduction algorithm found in two references: “Handbook of Applied Cryptography” Edited by Alfred J. Menezes et al and “A Course in Computational Algebraic Number Theory” by Henri Cohen. My new implementation in C# uses 64-bit integers and BigIntegers. Here are some results.
C++ Low Density Subset Sum Problem Solver Application Using the L3 Lattice Basis Reduction Algorithm Implemented by James Pate Williams, Jr. Utilizing the “Handbook of Applied Cryptography” Edited by Alfred J. Menezes Among Others
Subset Problem Solver Application Using the L3 Lattice Algorithm
See the following website for the used algorithms pages 119 to 121:
Blog Entry 01 11 2022 AES Exploration 2009 to 2018
Machine Cryptanalysis of Basic Cryptosystems by James Pate Williams, Jr. BA, BS, MSwE, PhD
In Winter and Spring 2018 I wrote a simple C# computer program to perform machine cryptanalysis of the following basic (elementary and easily breakable) cryptosystems:
- Affine Cipher Operating on Monographs and Digraphs
- Matrix Cipher
- Mono-alphabetic Cipher
- n-Rotor with Shifting Polyalphabetic Cipher
The key ingredient in this program is a relatively extensive English language dictionary.
Numerical Explorations 