Skip to main content
New
Stack Overflow Jobs powered by Indeed: A job site that puts thousands of tech jobs at your fingertips (U.S. only). Search jobs
13 votes
Accepted

Generate ANF from SBox

From TRUTH TABLE to ANF First write [6, 4, 7, 8, 0, 5, 2, 10, 14, 3, 13, 1, 12, 15, 9, 11] in that way: the columns of matrix are those numbers in $\mathbb{F_2^4}$. $$ \begin{bmatrix} 0&0&1&...
pico's user avatar
  • 158
13 votes

Generate ANF from SBox

This is useful to know in general. Given the Sbox map, generate the truth tables for the bits of the map. From the truth tables, obtain the algebraic normal form, via the Mobius transform. So, given ...
kodlu's user avatar
  • 22.6k
6 votes
Accepted

Degree vs index of regularity

There are a couple of definitions in the literature that each aim to capture an aspect of the degree $d$ to which a system of polynomial equations must be expanded before linear algebra on its ...
Alan's user avatar
  • 1,460
6 votes

What is linearization attack

A cryptosystem can be represented by multivariate equations and the analyzer tries to solve these equations efficiently in order to mount the algebraic attack. It is known that this is an NP-hard ...
kelalaka's user avatar
  • 48.7k
5 votes

Generate ANF from SBox

It is possible to use the SageMath, too. With the help of SBox package component_function(b): Return a Boolean function corresponding to the component function $b\cdot S(x)$ and from Boolean ...
kelalaka's user avatar
  • 48.7k
5 votes
Accepted

Derive $x$ when given $g,g^x$ and $g^{(1/x)}$?

Any group where you can derive $x$ from $g, g^x, g^{1/x}$ would also have the Discrete Log problem be equivalent to the (computational) Diffie-Hellman problem. Since this is not known to be true in ...
poncho's user avatar
  • 148k
4 votes
Accepted

Issue implementing Pollard's Rho for discrete logarithms

First of all, Pollard Rho finds an essentially random solution $(B - b) \gamma \equiv (a - A) \pmod{N}$. This randomness implies that if $N$ has a prime factor $p$, then $B - b$ has a probability $1/...
poncho's user avatar
  • 148k
4 votes

Determine complexity of a SAT problem

We do not know how to bound the complexity of a SAT problem. There are several special form SATs known to be solveable efficiently, but there is no finite list of such special problems. You can use a ...
Meir Maor's user avatar
  • 11.8k
3 votes

Evaluating Algebraic Complexity of a S-box

The interpolation of Sbox is based on Lagrange algorithm. the following three steps are used to calculate the interpolation of S-box: represent the S-box values as polynomial system, where P and C ...
hardyrama's user avatar
  • 2,126
2 votes
Accepted

Function to polynomial equation in GF(2)

The formula $$ d+e+ac+ae+bc+be+cd+de+ade+ace+abd+abc $$ is in algebraic normal form (ANF). That is the unique representation of our boolean function with respect to the $\mathbb F_2$-basis $\{a^ib^jc^...
yyyyyyy's user avatar
  • 12.1k
2 votes

Issue implementing Pollard's Rho for discrete logarithms

The problem is that Pollard Rho is not guaranteed to work, especially in very small examples where the order of the multiplicative group is 6. With larger groups, the modular inverse will almost ...
Christopher Swenson's user avatar
2 votes

Time Complexity of Exhaustive Search Algorithm

So, the only way must be an Exhaustive Search Algorithm As I mentioned in my comment, there are practical methods for nonhuge values of $m$ (and $m=52485332$ is not huge). Here is the outline of one ...
poncho's user avatar
  • 148k
2 votes

Finding Multiplicative Inverse In Field

For such small numbers, brute force search will do: by definition $a^{-1}\bmod p$ is the integer $x$ in $[0,p)$ with $a\,x\bmod p=1$. The desired $x$ can be found by trial and error. This requires ...
fgrieu's user avatar
  • 142k
2 votes

DH: Is it possible to solve for A private if all other variables are known with 90-bit modulus

Yes, this is totally feasible. Unless $p$ is purposely chosen as a safe prime, there's a good chance that's easy. Computing $a$ given $B$, $p$, and $C=B^a\bmod p$ is a Discrete Logarithm Problem in ...
fgrieu's user avatar
  • 142k
2 votes
Accepted

What is the difference between the 23 bi-affine and the 39 fully quadratic equations of the rijndael sbox?

Looking at appendix A of the eprint I'd say that the authors call a polynomial of algebraic degree at most $2$ bi-affine, if it contains some terms of algebraic degree $1$, and fully quadratic, if ...
someone's user avatar
  • 36
2 votes
Accepted

(Impossibility of?) Associative Pseudorandom Permutation

As mentioned by Meir Naor in the comments, what you are describing is impossible. The reason is that the associativity gives us leverage to distinguish the function from a random function. To do so an ...
Maeher's user avatar
  • 6,852
1 vote

Is it possible to break a DSA with k that increases statically?

Let's start by prettify the formula first, $$r = g^k \pmod q$$ $$s = {{h+xr}\over{k}}$$ The variables $r$ and $s$ are signature components, $x$ is private key, $h$ is message hash. Now 2 signatures: $$...
DannyNiu's user avatar
  • 9,400
1 vote
Accepted

How does big Galois groups yield better security in NTRU Prime?

It is hard to answer this question, as what you are reading is speculation on the part of Bernstein about a hypothetical weakness in standard lattice-based cryptography (i.e. using cyclotomics, with ...
Mark Schultz-Wu's user avatar
  • 13.3k
1 vote
Accepted

Data fingerprint using multiple multilinear polynomials

The point $P_i=f'(R_i),$ where $f'(x)=v_0 x+ v_0 x^2+v_0 x^3$ is a polynomial,.Normally one would also include a constant term in the polynomial. I will assume that for simplicity. In any case, since ...
kodlu's user avatar
  • 22.6k
1 vote

Time Complexity of Exhaustive Search Algorithm

This is more an answer to why the uniqueness of the sums effects the size so much that the case for $52485332$ becomes trivial (its way to long for a comment). When all sums must be unique, then they ...
jjj's user avatar
  • 469
1 vote

Need an XL Algorithm example

I recommend to read book "Algebraic Cryptanalysis Book by Gregory Bard". it has a simple example of XL algorithm chapter 12 page 213 (12.4 The XL Algorithm). after that you can develop sage/magma ...
hardyrama's user avatar
  • 2,126
1 vote

Generate ANF from SBox

Doing it via a simple and short Python snippet based on the Moebius answer. ...
Gregory Morse's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible