Category: Handbook of Applied Cryptography
Factorizations of Some Fibonacci Sequence Numbers, Lucas Sequence Numbers and Some Other Numbers Using Arjen K. Lenstra’s Free Large Integer Package and the Elliptic Curve Method (c) January 28, 2024, by James Pate Williams, Jr.
All of the following computations were performed on a late 2015 Dell XPS 8900 personal computer with a 64-bit Intel Core I7 processor @ 4.0GHz with 16GB of DDR2 RAM.
Factorization of Six Fibonacci Sequence Numbers:
Fibonacci 500
# digits 105
5 ^ 2 p # digits 1
15 c # digits 2
101 p # digits 3
401 p # digits 3
1661 c # digits 4
3001 p # digits 4
10291 c # digits 5
570601 p # digits 6
112128001 p # digits 9
1353439001 p # digits 10
28143378001 p # digits 11
5465167948001 p # digits 13
84817574770589638001 p # digits 20
158414167964045700001 p # digits 21
Runtime (s) = 1.206000
Fibonacci 505
# digits 106
5 p # digits 1
743519377 p # digits 9
44614641121 p # digits 11
770857978613 p # digits 12
960700389041 p # digits 12
12588421794766514566269164716286291055826556238643852856601641 p # digits 62
Runtime (s) = 1.959000
Fibonacci 510
# digits 107
2 ^ 3 p # digits 1
11 p # digits 2
61 p # digits 2
1021 p # digits 4
1597 p # digits 4
3469 p # digits 4
3571 p # digits 4
9521 p # digits 4
53551 p # digits 5
95881 p # digits 5
142445 c # digits 6
1158551 p # digits 7
3415914041 p # digits 10
20778644396941 p # digits 14
20862774425341 p # digits 14
81358225616651 c # digits 14
162716451241291 p # digits 15
Runtime (s) = 2.682000
Fibonacci 515
# digits 108
5 p # digits 1
519121 p # digits 6
5644193 p # digits 7
512119709 p # digits 9
84388938382141 p # digits 14
300367026458796424297447559250634818495937628065437243817852436228914621 p # digits 72
Runtime (s) = 7.861000
Fibonacci 520
# digits 109
131 p # digits 3
451 c # digits 3
521 p # digits 3
2081 p # digits 4
2161 p # digits 4
3121 p # digits 4
24571 p # digits 5
90481 p # digits 5
2519895 c # digits 7
21183761 p # digits 8
57089761 p # digits 8
102193207 p # digits 9
1932300241 p # digits 10
14736206161 p # digits 11
5836312049326721 p # digits 16
42426476041450801 p # digits 17
Runtime (s) = 5.155000
Fibonacci 525
# digits 110
2 p # digits 1
5 p # digits 1
421 p # digits 3
701 p # digits 3
3001 p # digits 4
3965 c # digits 4
4201 p # digits 4
141961 p # digits 6
2553601 p # digits 7
230686501 p # digits 9
8288823481 p # digits 10
82061511001 p # digits 11
19072991752501 c # digits 14
8481116649425701 p # digits 16
17231203730201189308301 p # digits 23
Runtime (s) = 2.026000
Factorization of Six Lucas Sequence Numbers
Lucas 340
113709744839525149336680459091826532688903186653162057995534262332121127
# digits 72
7 p # digits 1
2161 p # digits 4
5441 p # digits 4
897601 p # digits 6
23230657239121 p # digits 14
17276792316211992881 p # digits 20
3834936832404134644974961 p # digits 25
Runtime (s) = 109.103000
Lucas 345
# digits 73
2 ^ 2 p # digits 1
31 p # digits 2
461 p # digits 3
1151 p # digits 4
1529 c # digits 4
324301 p # digits 6
686551 p # digits 6
1485571 p # digits 7
4641631 p # digits 7
19965899801 c # digits 11
117169733521 p # digits 12
3490125311294161 p # digits 16
Runtime (s) = 0.032000
Lucas 350
13985374084677485786380981408251904922622980674054858121032362563653278123
# digits 74
3 p # digits 1
401 p # digits 3
2801 p # digits 4
11521 c # digits 5
28001 p # digits 5
570601 p # digits 6
12317523121 p # digits 11
248773766357061401 p # digits 18
7358192362316341243805801 p # digits 25
Runtime (s) = 21.047000
Lucas 355
69362907070206748494476200566565775354902428015845969798000696945226974645
# digits 74
5 p # digits 1
4261 p # digits 4
6673 p # digits 4
75309701 p # digits 8
309273161 p # digits 9
46165371073 p # digits 11
9207609261398081 p # digits 16
49279722643391864192801 p # digits 23
Runtime (s) = 40.726000
Lucas 360
769246427201094785080787978422393713094534885688979999504447628313150135520
# digits 75
2 ^ 5 p # digits 1
3 ^ 2 p # digits 1
23 p # digits 2
41 p # digits 2
105 c # digits 3
107 p # digits 3
241 p # digits 3
2161 p # digits 4
2521 p # digits 4
3439 c # digits 4
8641 p # digits 4
20641 p # digits 5
103681 p # digits 6
109441 p # digits 6
191306797 c # digits 9
10783342081 p # digits 11
13373763765986881 p # digits 17
Runtime (s) = 0.032000
Lucas 365
19076060504701386559675231910437330047906343529583769121365013189782992678011
# digits 77
11 p # digits 2
151549 p # digits 6
514651 p # digits 6
7015301 p # digits 7
8942501 p # digits 7
9157663121 p # digits 10
11899937029 p # digits 11
3252336525249736694804553589211 p # digits 31
The following two numbers were first factorized by J. M. Pollard on an 8-bit Phillips P2012 personal computer with 64 KB RAM and two 640 KB disc drives. The times required by Pollard were 41 and 47 hours.
2^144-3
22300745198530623141535718272648361505980413
# digits 44
492729991333 p # digits 12
45259565260477899162010980272761 p # digits 32
Runtime (s) = 0.086000
2^153+3
11417981541647679048466287755595961091061972995
# digits 47
5 p # digits 1
11 p # digits 2
600696432006490087537 p # digits 21
345598297796034189382757 p # digits 24
Runtime (s) = 0.676000
Partial factorization of the Twelfth Fermat Number 2^4096+1
# digits 1234
114689 p # digits 6
26017793 p # digits 8
63766529 p # digits 8
190274191361 p # digits 12
Runtime (s) = 1532.878000
Multiple Precision Arithmetic in C++ Implemented by James Pate Williams, Jr.
I have developed a long integer package in C++ using H. T. Lau’s “A Numerical Library in C for Scientists and Engineers”. That library is based on the NUMAL Numerical Algorithms in Algol library. I use 32-bit integers (long) as the basis of the LongInteger type. The base (radix) is 10000 which is the largest base using 32-bit integers. As a test of the library, I use Pollard’s original rho factorization method. I utilized the Alfred J. Menezes et al “Handbook of Applied Cryptography” Miller-Rabin algorithm and ANSI X9.17 pseudo random number generator with Triple-DES as the encryption algorithm. I translated Hans Riesel Pascal code for Euclid’s algorithm and the power modulus technique. I don’t use dynamic long integers a la Hans Riesel’s Pascal multiple precision library. The single precision is 32 32-bit longs and multiple precision 64 32-bit longs.
Here is a typical factorization:
Number to be factored, N = 3 1234 5678 9012
Factor = 3
Is Factor prime? 1
Factor = 4
Is Factor prime? 0
Factor = 102 8806 5751
Is Factor prime? 1
Function Evaluations = 6
Number to be factored, N = 0
The first number of N is the number of base 10000 digits. I verified that 10288065751 was prime using Miller-Rabin and the table found online below:
http://compoasso.free.fr/primelistweb/page/prime/liste_online_en.php
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
Blog Entry of Wednesday February 2, 2022 by James Pate Williams, Jr.
Blog Entry of January 27, 2022 by James Pate Williams, Jr
Five Stream Ciphers Created from Five Pseudorandom Number Generators Built Using the Tests of FIPS 140-1 by James Pate Williams, BA, BS, MSwE, PhD
The five pseudorandom number generators are:
- Triple-AES based ANSI X9.17 PRNG
- Triple-DES based ANSI x9.17 PRNG
- RSA based PRNG
- Micali-Schnorr PRNG
- Blum-Blum-Shub PRNG
Five stream ciphers were created using 1 to 5. Screenshots of the C# application follow:
The pass phrase optimally should consist of 147 ASCII characters. If the number of pass phrase ASCII characters is less than 147 then more random ASCII characters are added using the standard C# pseudorandom number generator seeded with the parameter named Seed. The user defined parameter k is used by RSA, Micali-Schnorr, and Blum-Blum-Shub pseudorandom number generators. It is the approximate bit length of the large composite number composed of two large probable prime numbers. The real key lengths of all the stream ciphers is about 1024-bits for 1, 3, 4, and 5 and 296-bits for 2. I’d strongly suggest using 1 and/or 5.
Tests of Six Pseudorandom Number Generators (PRNGs) Using the Now Superseded FIPS 140-1 by James Pate Williams, Jr. BA, BS, MSwE, PhD
This blog explores six pseudorandom number generators which are enumerated as follows:
- Standard C# PRNG
- Triple-AES PRNG
- Triple-DES PRNG
- RSA Based PRNG
- Micali-Schnorr PRNG
- Blum-Blum-Shub PRNG
Here is the order in terms of run-times from the fastest to the slowest: 1, 2, 3, 6, 5, 4.
PRNG Tests Using the Now Superseded FIPS 140-1 by James Pate Williams, Jr., BA, BS, MSwE, PhD
This blog post is dedicated to Section 5.3.1 ANSI X9.17 generator page 173 with 5.11 Algorithm and Section 5.4.4 Five basic tests pages 181-183 especially 5.32 Note of the Handbook of Applied Cryptography by Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone. I developed a PRNG test program for three PRNGs namely, Triple-AES, Triple-DES, and the C# built-in PRNG.
Each time an algorithm is run a randomly generated key is generated based on the time of day and the C# built-in PRNG with a key space of 2147483647 possible seeds. Triple-AES requires a 147 7-bit ASCII key and part of a similar key is used to construct the 296-bit Triple-DES key material. Now onto my C# Windows Forms application’s screenshots.
We use the five basic statistical tests of Chapter 5 Section 5.4.4 which are as follows:
- Monobit Test also Known as the Single Bit Frequency Test
- Serial Test also as the Two-Bit Frequency of Occurrence Test
- Poker Test
- Runs Test (Not to be confused with Montezuma’s Revenge)
- Autocorrelation Test
Below is a copy of a recent email of mine concerning Secret Key Exchange or Distribution:
The linchpin and point of greatest vulnerability in any secret key cryptographic system is the key exchange mechanism. Now suppose that we are living in a post quantum computer world. This means that traditional public key cryptosystems such as RSA (integer factorization problem based) and elliptic curve public key cryptography (discrete logarithm problem based) are effectively broken. That implies that any public key based cryptographic key exchange is compromised over communication channels where Eve, the classical eavesdropper, is listening in on the key exchange between Alice and Bob. Quantum cryptography over fiber optic channels allows the communication endpoints to detect the eavesdropper and thus abort a potentially compromised key exchange. However, quantum cryptography is not readily available everywhere on the vast Internet. The rest of this email missive is devoted to other more exotic means of secret key exchange.
Human to human key exchange is optimal provided that all human beings in the loop are trustworthy. A good way to exchange secret keys is via a diplomatic courier with a diplomatic pouch and the key bits are concealed by a steganographic means.
Now suppose an adversary of an English speaking and reading country has two agents or human intelligence operatives that have infiltrated the country. Further both agents have the same 1024-bit seeded pseudorandom number generator-based stream cipher on their desktops and/or laptops for secure communications. That means they must somehow pass 147 secret 7-bit printable ASCII characters of information between one another for each quasi-one-time pad message. Each character represents 7 bits of the key and there are 5 bits left over after construction of each key. Also, suppose an actual face-to-face meeting between the two spies is inadvisable. Enter the text based social media or library book code. Now suppose the two spies are connected to one another via Facebook but are afraid to use text messaging for direct key exchange or clandestine communication. The solution is to use a shared Facebook page of text to construct the secret key. One spy shares a Facebook post containing at least 147 English characters and the other spy looks up the post. Both spies cut and paste the first 147 English characters of the post into a key constructing application. Voila, now both spies can communicate using their handy dandy stream cipher and email and/or cell phone text messaging of encrypted data in the form of three-digit decimal numbers. An alternative key exchange could be by the classic and readily available book code. Assume both spies have access to the same library, but not concurrent access. Both somehow agree to go and copy 147 characters from the same book in the library’s reference section. They write down the passage and take it home to enter the text into the key generator. Again, we have a means of clandestine key exchange.
Numerical Explorations 