NumberWorld

Detecting primes in deterministic polynomial time was a goal for hundreds of years. In 2002, a major breakthrough occurred in number theory: for the first time, a proof was published showing how to determine, in deterministic polynomial time, whether a given integer $n$ is prime. The resulting method is now known as the AKS algorithm , named after its authors Agrawal, Kayal, and Saxena. For their work, they received two major international awards: the Gödel Prize and the Fulkerson Prize. Of course, even before 2002, finding large prime numbers was far from hopeless. In fact, the algorithms used in practice today are essentially the same as those used before AKS, because they are extremely efficient. However, before AKS, all known efficient primality tests had one of the following drawbacks:

Most broken cryptosystems do not fail because the underlying mathematics is wrong. They fail because a seemingly harmless implementation choice quietly destroys the hard problem the scheme was supposed to rely on. In this post, I show three examples of exactly that: a Diffie–Hellman setup with weak primes, a matrix-based variant that leaks the exponent through Jordan blocks, and an elliptic-curve implementation that skips the point-on-curve check and can be tricked onto a malicious curve. None of these failures look dramatic at first glance. That is exactly why they are dangerous.

In this article, we demonstrate a subtle but devastating backdoor in finite-field Diffie–Hellman. By computing public keys modulo $p^2$ instead of $p$ while restricting the secret exponent to $x \leq p-1$, the discrete logarithm becomes efficiently recoverable using Fermat quotients. We show the full derivation and provide a working Sage implementation. Backdoors are always bad — but they are catastrophic when they are embedded in a fundamental primitive like Diffie–Hellman key exchange. If your browser shows a green lock, you assume your connection is secure. But what if the implementation of Diffie–Hellman contains a tiny change that looks harmless in code review — and yet allows an attacker to recover the private exponent in milliseconds? In this post I’ll show a nasty little backdoor that requires only a tiny modification: using a modulus of $p^2$ instead of $p$, while keeping the secret exponent bounded by $p$ This ...

For decades, elliptic curves were regarded as beautiful but highly theoretical objects. While elliptic curves over finite fields naturally form groups, one fundamental problem remained computationally difficult: counting points on elliptic curves . In particular, determining the exact size of the group \( E(\mathbb{F}_p) \) was infeasible for general curves. Before the mid-1980s, counting points on elliptic curves was practical only for very special families, such as curves with complex multiplication. This severely limited their cryptographic applications. Early public-key cryptography therefore relied instead on multiplicative groups of finite fields, where the group order is easy to compute. Everything changed with Schoof’s algorithm. For the first time, it showed that counting points on elliptic curves over finite fields can be done in polynomial time. This breakthrough removed a major barrier to using elliptic curves in cryptography. Today, efficient point coun...

One of the most charming things about modern cryptography is that it often rests on questions we still don’t fully understand. Even after decades of research, some of the most central assumptions — the kind that protect millions of TLS handshakes every second — remain only partially mapped. A perfect example is the relationship between two cornerstone problems in cyclic groups: the Discrete Logarithm (DL) problem and the Computational Diffie–Hellman (CDH) problem. At first glance, DL seems clearly stronger than CDH. If you can solve discrete logs, you can obviously solve CDH: given $g^x$ and $g^y$, you recover $x$ and $y$, and then compute $g^{xy}$. The reverse implication is where the mystery begins. Suppose you had access to a machine — an oracle — that, given $(g^x,g^y)$, instantly returns $g^{xy}$. Could you then use this ability to compute discrete logarithms efficiently?

⬛ Some of you may be familiar with this situation. From time to time you find yourself thinking about a new approach to a problem that you know is difficult. And although you know that you should probably be doing something more productive, you try new ideas to tackle the problems. And every now and then you stumble across a more or less basic fact that prevents your idea from working. I will try to give some examples that may surprise you. I will focus on the three main problems: discrete logarithm problem , factorization problem and the class number computation problem. Often the examples come from situations that similar to:     Alice: " I have a great idea. What if you could find some object O that has property P and Q ."     Bob: " Perfect, O is well known and P and Q seem not that restrictive ." A few days later.     Alice: " I can not find such an object. All objects either have P or Q but not both ."      Bob: "...

Cryptographic standardisation is usually presented as a process of selecting winners. Candidates are submitted, experts evaluate them, weaker designs are eliminated, and the strongest algorithms eventually become standards. The NIST Post-Quantum Cryptography standardisation process followed this general pattern, but with an unusual and important twist: two serious candidates survived almost until the end, only to suffer devastating cryptanalytic breaks. Rainbow was effectively eliminated late in the third round, while SIKE was broken shortly after advancing to the fourth round. And by this time already several years of research was done. To me, these events are among the most remarkable aspects of the entire NIST process. They demonstrate both how difficult it is to evaluate new cryptographic assumptions and why public cryptanalysis must remain at the centre of cryptographic standardisation. A global experiment i...

▍The Hidden Subgroup Problem is an important problem from Computer Science / Mathematics and actually covers several well known problems as a special case. The formal statement of the problem is: Definition [Hidden Subgroup Problem (HSP)]  Let $\mathbb{G}$ be a group and $\mathbb{H}$ an unknown subgroup of $\mathbb{G}$, i.e., $\mathbb{H} \leq \mathbb{G}$. Let $S$ be any set and $f$ be a function that maps the group elements of $\mathbb{G}$ to $S$, i.e., $f: \mathbb{G} \rightarrow S$. The function $S$ has the special property that it can distinguish cosets of $\mathbb{H}$: $$ f(e_1) = f(e_2) \Leftrightarrow e_1\mathbb{H} = e_2\mathbb{H} $$ The Problem is, given $\mathbb{G}$ and access to the function $f$, to determine a generating set for the subgroup $\mathbb{H}$ ∎  The notation $e\mathbb{H}$ denotes the coset $$e\mathbb{H} = \left\{eh | h \in \mathbb{H}\right\}$$. Problems that can be described as an instance of the HSP are for example: ...

We start with a very brief primer to Binary Quadratic Forms (BQF). For more information ⦗1⦘ is a very good source to start with. 　A Binary Quadratic Form is a polynom of the form $Q(x,y) = ax^2+bxy+cy^2$ with integer coefficients. We focus on integer BQF, i.e., $x,y \in \mathbb{Z}$. Often one is only interested in the behaviour of the coefficients $a,b,c$ and in those cases one refers to a BQF simply by the triple $(a,b,c)$. Further, the integer $D$ defined as: $$D = b^2 - 4ac$$ is called the discriminant of $(a,b,c)$. 　A positive definite BQF $(a,b,c)$, i.e. $D < 0, a > 0$, is reduced if $-a < b < a < c$. Gauss observed, that all reduced BQF with the same discriminant form an abelian group and he gave a composition algorithm for those group elements. This group is called the class group and is usually denoted as $\mathcal{Cl}(D)$. The size of the group has a special name and is called the class number $h(D)$. Informally spoken, the class group $\mathcal{Cl}(D)$ ...

This blog post is about De Bruijn sequences and its relationship to cryptography. We focus here on De Bruijn sequences over the alphabet $A=\{0,1\}$. Definition [De Bruijn sequence (binary)] .   A binary string of length $2^n$ is called a De Bruijn sequence of order $n$ if each possible $n$-bit string occurs exactly once (incl. wrap-around) as a substring.  Picture 1 - DeBruijn graph for n=3 De Bruijn sequences are the shortest possible bitstring that contains all possible $n$-bit substrings. For each $n$ there are $$\frac{2^{2^{n-1}}}{2^n}$$ possible De Bruijn sequences. For example, a De Bruijn sequence of order $n=3$ is $$00011101$$ and of order $n=4$ is $$0000101100111101$$ There are several ways to create De Bruijn sequences. One way is walk along an  Hamiltonian Cycle in the corresponding De Bruijn graph (see Picture 1) . A De Bruijn graph is a directed graph of degree $2$ which has $2^n$ vertices. There is an edge from vertex $i$ to the two vertices $$(2i\;...

❚ This  post is related to a paper of mine, that will get published around the end of October this year in the Journal of Groups, Complexity and Cryptography  (GCC). Some people may think, when they read the headline of this post, this must be a post about Shor's quantum factoring/dlog algorithm, because it is well known that dlogs and factoring can not be solved in polynomial number of arithmetic steps otherwise.   But this is not true. This sounds very unintuitive, because in cryptography we nearly always work with finite fields, where the bit length is restricted by the size of the modulus and the complexity of an algorithm is hence often measured as the number of arithmetic steps. But of course you can do this, if you increase the available space . It is not obvious how to do it, but Adi Shamir [1] already showed in 1979 how this could be done, it you allow integers in memory/registers that are of exponential size.

There is new hope, new hope for a feasible algorithm that survives Quantum Computer attacks and will give us secure cryptographic key agreements in the future. It is based on Ring-LWE , where LWE is the abbreviation for Learning With Errors and Ring simply means, that you are working over some ring structure. Roughly you can put LWE in the corner of lattice based cryptography, which is one of the contestants for post-quantum cryptography. The other contestants are multivariate equations and coding based cryptography (i.e. McEliece and Niederreiter). In the meantime, one major application of LWE is also fully homomorphic encryption [4]. The underlying scheme for the $\text{NewHope}$ algorithm was proposed by Jintai Ding, Xiang Xie and Xiaodong Lin [1] in 2012, then got improved by Peikert in 2014 [2]. Joppe W. Bos, Craig Costello, Michael Naehrig and Douglas Stebila [3] presented an implementation in 2015. The next major improvement by Erdem Alkim, Léo Ducas, Thomas...

The ABC-Conjecture is a very famous conjecture in Number Theory which is perhaps not a conjecture anymore if it the proof of Shinichi Mochizuki will turn out to be correct. I can not say anything useful about proving this conjecture, but i thought about its application for a while. Let me state the stronger version of the conjecture due to Baker [1] ; ABC-Conjecture (strong, explicit version) Given co-prime integers $a,b,c$ with $a + b = c$ then $$ c < (\text{rad}(abc))^{1.75}$$ The operator $\text{rad}$ (=radical) means the product of the distinct prime numbers dividing $n$. The version was derived from the (following) explicit ABC-Conjecture, also due to Baker: ABC-Conjecture (explicit version) Given co-prime integers $a,b,c$ with $a + b = c$ and let $\omega(n)$ be the number of distinct prime factors of $n$ then $$c < \frac{6}{5}\text{rad}(abc)\frac{(\log(\text{rad}(abc)))^{\omega(abc)}}{\omega(abc)!}$$ Assume you have co-prime integers $a,b,c$, wlog...

❚ In the previous post , i gave a short introduction about homomorphic encryption and presented the DGHV scheme [5] as an example. The scheme was published in 2010 and got several important updates from Coron et al. in the following papers: [1], 2011 : The first improvement enhances the original system by reducing the size of the public key from $\mathcal{\tilde{O}}(\lambda^{10})$ to $\mathcal{\tilde{O}}(\lambda^{7})$. The idea is, to publish fewer elements that can be combined on-the-fly to reach a larger public key if necessary. To achieve this, they need the already discussed optimization to set $x_0 = pq_0$, hence they settle the system on the stronger partial approximate common divisor problem . [2], 2012 : In this paper, they further reduce the size of the public key down to $\mathcal{\tilde{O}}(\lambda^5)$. Instead of storing the large numbers $r_i+pq_i$, they only store a public seed $\text{se}$ and a set of small $\delta_i$ values that are of size $~p$. To recover the or...

1 :: What is homomorphic encryption ❚ H o momorphic encryption was for many years the holy grail in cryptography after it was introduced by Rivest, Adleman and Dertouzos [5] in the year 1978, shortly after the first two authors together with A. Shamir published the famous RSA scheme. The idea is simple and its usefulness is obvious: Find an encryption system, that allows to add and multiply ciphertexts, such that the executed operations on the ciphertexts transfer to the plaintexts. Simplified-Example . Input $m_1 = 4$, $m_2 = 9$ and $m_3 =5$. Then encrypt these three values using a public key PK \begin{align*}  \text{Enc}(m_1,PK) & = \text{Enc}(4,PK) = 11 = c_1\\  \text{Enc}(m_2,PK) & = \text{Enc}(9,PK) = 21 = c_2\\  \text{Enc}(m_3,PK) & = \text{Enc}(5,PK) = 13 = c_3 \\ \end{align*} Then you compute $$ (c_1 + c_2)*c_3 = (11+21)*13 = 416 = C $$ Next, you decrypt the result $C$ using the secret key SK, which leads magically to $$\text{Dec}(C,SK) = \te...

❚ Several weeks ago , i heard a nice talk from one of my colleagues about the Coppersmith method and it application to factoring integers. It is a very powerful method and can, e.g., be applied if partial information of $p$ or $q$ is known, the factors $p$ and $q$ of $N=pq$ have a small differences or to obtain a deterministic algorithm that returns a factor if a multiple of $\varphi(N)$ is known. The trigger for the talk was a discussion about the risk if the inverse of one factor modulo the other factor of an RSA modulus is leaked. That means knowing the following integer $I$: $$I \equiv p^{-1} \pmod{q},\;p,q \in \mathbb{P},\;N=pq$$ Since the Coppersmith method is very powerful it is actually not surprising that it could be used to accomplish this task, at least partially. ❰Coppersmith's Theorem❱ Let $0 < \beta < 1$ and $c,N \geq 1$ and $f \in \mathbb{Z}[x]$ be a monic polynomial of degree $\delta$. The set of all integer $a \in \mathbb{Z}$ with $$\gcd(f(a),N) \geq N...

For convenience, i restate the problem definition here: Problem-Definition . Assume you have an integer interval $I = [0,n]$ and a set $Z$ that consists of tuples $(x,s(x))$, with $x \in_R I$ and $s(x) = \text{sign}(\sin(2x\pi/p))$. Find the secret parameter $p$. Formulated in words, the set $Z$ contains randomly distributed integers from $I$ enriched with the information if a certain (but fixed) sinus wave travels above or below that integer (i.e. the sign value) and your goal is to find that particular sine wave. Heuristically, $\log p$ points should be sufficient, and in the first part on this topic, i described an easy instance of this problem that indeed finds $p$ using only $\mathcal{O}(\log p)$ points. Then i showed what causes the algorithm to fail if the problem instance gets a little bit more complicated. The algorithm then fails because the solution space falls apart (this could be very well shown visually if the solution spaces are drawn on a unity disk...

D uring the last months i spent some of my free time to read several books and interesting articles. E.g. " The Golden Ticket : P, NP, and the Search for the Impossible " by Lance Fortnow or Scott Aaronson's " Quantum Computing since Democritus ". In the former the author describes in one chapter how the world would look like if P = NP. He is by no way the first who thinks and writes about this, but he did it in a very extensive and pictured way. It was intriguing to read what kind of things would become possible if this rather mathematical problem would be solved. The world can be described at best with " Everything that we can quickly recognize as being a good solution for a problem, we can find quickly " But more on this later. Of course, an existential proof would not change much, besides the receipt of one million dollars from the clay institute. If you just prove that there has to be an algorithm that could solve the traveling salesmann probl...

Auxiliary Input helps The discrete logarithm problem with auxiliary input is defined as the problem to compute the integer $e$ given the input $(g,g^e = r,\mathcal{G})$, whereof $\mathcal{G}$ is an abelian group and $g$ is of prime order $p$ if one knows the additional input $$\left(g^{e^2},g^{e^3},...,g^{e^d}\right) \in \mathcal{G}^d$$ In [1] Jung Hee Cheon presents an algorithm which solves the problem in $\mathcal{O}(\sqrt{p/d} + \sqrt{d})$ using $$\mathcal{O}\left(\max\left(\sqrt{(p-1)/d},\sqrt{d}\right)\right)$$ space if $d | (p-1)$. The algorithm works even if the input is reduced to $(g,g^e=r,\mathcal{G},g^{e^d},d)$ only. If $p|(p+1)$ he shows how to solve the problem given the full input in $\mathcal{O}\left(\sqrt{p/d} + d\right)$ using the same amount of space as in the case $p|(p-1)$.

The discrete logarithm problem is one of the cornerstones of modern asymmetric cryptography. Several algorithms exist and each approaches the problem in different ways. For example, the Pohlig-Hellman algorithm exploits smooth group orders, the index calculus algorithm uses a small set of known discrete logarithms in order to combine them to solve the problem in question and Pollards Rho-Algorithms makes use of the birthday paradox. I am not aware of any approach that makes use of the fact, that the residues $r_i$ in the group $\mathcal{G} \subseteq \mathbb{F}_p$ generated by the element $g$ are often nearly equal distributed. Ok, this is not always true and there are some deep and highly non-trivial theorems about the distribution of these group elements. But for our purposes we can assume that the average size of a group element is $(p-1)/2$. That means, if we assume that $g$ is a primitive root, hence $\mathcal{G} = \mathbb{F}^*_p$, and $r_i \equiv g^i\pmod{p}$ it holds: $$ \s...