Showing posts with label cryptography. Show all posts
Showing posts with label cryptography. Show all posts

Wednesday, 24 February 2021

Elliptical Curves

I recently read an interesting article in Quanta Magazine that involved elliptic curves. It's a fairly high level article but an excerpt read:

Their starting point was one of the central objects in number theory: elliptic curves. Just like circles and lines, elliptic curves are both numbers and shapes. They are pairs of numbers, \(x\) and \(y\), that serve as solutions to an algebraic equation like \(y^2 = x^3 − 2x\). The graph of those solutions creates a geometric shape that looks vaguely like a vertical line extruding a bubble.

This was followed by the diagram shown in Figure 1:


Figure 1

It turns out that these elliptic curves are very important in cryptography as this following YouTube video explained:


Many elliptic curves can be written as \(y^2=x^3+ax+b\) and all the curves shown in Figure 1 are of this type. What's of interest to me is that there are integer solutions to these sorts of equations, in other words there are points \( (x,y) \) such that \(x\) and \(y\) are both integers. These could be termed elliptic Diophantine equations.

Let's consider \(y^2=x^3-x+1\) as a particular example (the graph is shown in Figure 1, bottom left). When \(x=0\), \(y \pm 1\) but what about when \(y=0\)? Here we have \(x^3-x+1=0\) and there are three solutions, two complex and one real. What is the real solution? $${\left(\frac{1}{18} \, \sqrt{23} \sqrt{3} - \frac{1}{2}\right)}^{\frac{1}{3}} + \frac{1}{3 \, {\left(\frac{1}{18} \, \sqrt{23} \sqrt{3} - \frac{1}{2}\right)}^{\frac{1}{3}}} \approx -1.3247$$So let's check what integral solutions there are between -1 and 100. Figure 2 shows the points that satisfy (permalink):


Figure 2

Extending the range to one million does not throw up any new points so these seem to be the only points that are integers. I have a book that deals with this very subject that is described as follows:
This book presents in a unified and concrete way the beautiful and deep mathematics - both theoretical and computational - on which the explicit solution of an elliptic Diophantine equation is based. It collects numerous results and methods that are scattered in the literature. Some results are hidden behind a number of routines in software packages, like Magma and Maple; professional mathematicians very often use these routines just as a black-box, having little idea about the mathematical treasure behind them. Almost 20 years have passed since the first publications on the explicit solution of elliptic Diophantine equations with the use of elliptic logarithms. The "art" of solving this type of equation has now reached its full maturity. The author is one of the main persons that contributed to the development of this art. The monograph presents a well-balanced combination of a variety of theoretical tools (from Diophantine geometry, algebraic number theory, theory of linear forms in logarithms of various forms - real/complex and p-adic elliptic - and classical complex analysis), clever computational methods and techniques (LLL algorithm and de Weger's reduction technique, AGM algorithm, Zagier's technique for computing elliptic integrals), ready-to-use computer packages. A result is the solution in practice of a large general class of Diophantine equations.
This is rather too detailed for me but the mention of Magma and Maple make me wonder what tools SageMath has to offer in terms of the solution of elliptic Diophantine equations. The book was published in August of 2013. As it turns out SageMath offers two commands. For the equation \(y^2=x^3+ax+b\), the commands are:

E=EllipticCurve([\(a,b\)])
E.integral_points()

For the case of \(y^2=x^3-x+1\), this produces the output (\(a\)=-1 and \(b\)=1):

[(-1 : 1 : 1), (0 : 1 : 1), (1 : 1 : 1), (3 : 5 : 1), (5 : 11 : 1), (56 : 419 : 1)]

The output is a little confusing but it would seem that the final 1 in each triplet signifies that the middle number can be positive or negative. It is thus equivalent to:

[(-1, ±1), ((0, ±1)), (1, ±1), (3, ±5), (5, ±11), (56, ±419)]

This is what is got earlier using my longer method. Elliptic curves is a big topic and I've only scratched the surface here. Figure 3 shows the points on the curve except for (56, ±419).


Figure 3: created using GeoGebra Classic

Sunday, 20 January 2019

The Mersenne Twister

I stumbled upon the Mersenne Twister after investigating Pseudorandom Number Generators (PRNGs) stimulated by an article about a hacker who had made a speciality of exploiting weaknesses in the PRNGs incorporated into certain types of slot machines.

Here is an excerpt from the article:
In the course of reverse engineering Novomatic’s software, Alex encountered his first PRNG. He was instantly fascinated by the elegance of this sort of algorithm, which is designed to spew forth an endless series of results that appear impossible to forecast. It does this by taking an initial number, known as a seed, and then mashing it together with various hidden and shifting inputs—the time from a machine’s internal clock, for example. Writing such algorithms requires tremendous mathematical skill, since they’re supposed to produce an output that defies human comprehension; ideally, a PRNG should approximate the utter unpredictability of radioactive decay.
The intriguingly named Mersenne Twister is described thus by Wikipedia:
The Mersenne Twister is a pseudorandom number generator (PRNG). It is by far the most widely used general-purpose PRNG. Its name derives from the fact that its period length is chosen to be a Mersenne prime. 
The Mersenne Twister was developed in 1997 by Makoto Matsumoto and Takuji Nishimura. It was designed specifically to rectify most of the flaws found in older PRNGs. 
The most commonly used version of the Mersenne Twister algorithm is based on the Mersenne prime \(2^{19937}−1\). The standard implementation of that, MT19937, uses a 32-bit word length. 
The Mersenne Twister is the default PRNG for the following software systems: Microsoft Excel, GAUSS,  GLib, GNU Multiple Precision Arithmetic Library, GNU Octave, GNU Scientific Library, gretl, IDL, Julia,  CMU Common Lisp, Embeddable Common Lisp, Steel Bank Common Lisp, Maple, MATLAB, Free Pascal, PHP, Python, R, Ruby, SageMath, Scilab, Stata.
I don't want to delve too deeply into the how the Mersenne Twister actually generates its random numbers. However, the following article provides a simple overview of how it works.

How does the Mersenne Twister work?

Posted February 2016

Someone asked that question on reddit, and so I replied with a high level answer that should provide a clear enough view of the algorithm:

From a high level, here's what a PRNG is supposed to look like (DIAGRAM 1):


DIAGRAM 1

You start with a seed (if you re-use the same seed you will obtain the same random numbers), you initialise it into a state. Then, every time you want to obtain a random number, you transform that state with a one-way function \(g\). This is because you don't want people to find out the state out of the random output.

You want another random number? You first transform the state with a one way function
\(f\): this is because you don't want people who found out the state to be able to retrieve past states (forward secrecy). And then you use your function \(g\) again to output a random number.

Mersenne Twister (MT) is like that, except:
  • your first state is not used to output any random numbers
  • a state allows you to output not only one, but 624 random numbers (although this could be thought as one big random number)
  • the \(g\) function is reversible, it's not a one-way function, so MT it is not a cryptographically secure PRNG.
With more details, here's what MT looks like (DIAGRAM 2):


DIAGRAM 2

The \(f\) function is called "twist", the \(g\) function is called "temper". You can find out how each functions work by looking at the working code on the wikipedia page of MT.

*********************************

The slot machine hacking via knowledge of the PRNG within got me thinking about my own gambling on Lotto, a vice I indulge in weekly. How are the lotto numbers selected? Are there physical, numbered balls involved or is a PRNG used? There's no shortage of sites that will generate random numbers for you to enter in any lottery of your choosing but how are the actual winning numbers generated? Well it seems that the numbers are physically selected in Australian lotteries as shown in the following video:


However, Lucky Lotteries is different.


To quote from the website:
Lucky Lotteries is a raffle style jackpot game that guarantees over 10,000 prizes in every draw! Unlike other lottery games, each number is unique so there is no sharing of prizes. 
There are two Lucky Lotteries games – Super Jackpot and Mega Jackpot. 
Each game has a set amount of numbers per draw and once all available numbers are sold, the winning numbers are drawn using a random number generator.
So clearly a PRNG is used in certain lotteries. Of course, I use SageMath extensively and so it's of interest to know about what PRNG it uses. SageMath documentation explains that:
It is possible to select which random number generator drives the sampling as well as the seed. The default is the Mersenne twister. Also available are the RANDLXS algorithm and the Tausworthe generator (see the gsl reference manual for more details). These are all supposed to be simulation quality generators. For RANDLXS use rng = 'luxury' and for tausworth use rng = 'taus': 
sage: T = RealDistribution('gaussian', 1, rng = 'luxury', seed = 10)

Sunday, 4 October 2015

Brilliant Numbers

8 is the smallest 3-brilliant number
Recently, my day count returned a pair of brilliant numbers: 24287 and 24289. A brilliant number is defined by Peter Wallrodt as a number with two prime factors of the same length (in decimal notation). These numbers are generally used for cryptographic purposes, and for testing the performance of prime factoring programs. It is possible to define n-brilliant numbers as the product of n prime numbers of the same length (source).

By this definition, 24287 = 149 x 163 and 24289 = 107 x 227 are 2-brilliant numbers. What's interesting about these two brilliant numbers is that they are consecutive (because there are no even brilliant numbers greater than 14). As is explained in OEIS A083284:


The only consecutive brilliant numbers are {9, 10} and {14, 15}; and for n > 14 there are no brilliant constellations of the form {n, n+(2k+1)} or equivalently {n, 2k+n+1} with k >= 0. Proof: One of n and 2k+n+1 will be even. And there are no even brilliant numbers > 14 since they must have the form 2*p where p is a prime having only one digit.

Here is the list of the smaller of the brilliant numbers pairs (from OEIS A083284):

Numbers n such that n and n+2 are both brilliant numbers, where brilliant numbers are semiprimes whose prime factors have an equal number of decimal digits, or whose prime factors are equal.

4, 527, 779, 869, 899, 1079, 1157, 1271, 1679, 4187, 6497, 6887, 24287, 24881, 25019, 29591, 35237, 37127, 37769, 38807, 39269, 39911, 41309, 43361, 44831, 45347, 46001, 46127, 47261, 48509, 48929, 51809, 52907, 54389, 55481, 55751, 55961