# Questions tagged [modular-arithmetic]

Modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" upon reaching a certain value… the modulus.

483 questions
Filter by
Sorted by
Tagged with
52 views

### Is there any lemma or theorem for finding the following output linear masks?

Let $\operatorname{rotl32}(x,2)$ be rotating a 32 bit word $x$ to the left by 2, and $+$ be modular addition on 32 bit, meaning$\pmod{2^{32}}$; and $Z_2^{32}$ be the space of all 32 bit words. Now we ...
• 39
1 vote
147 views

### What’s the fastest known Koblitz curve addition law for FPGA that maximizes the per-LUT throughput?

The addition or multiplication laws used by large mainstream libraries achieve faster speed by using many many more operations in order to avoid larger numbers. And my problem is here: faster speeds ...
• 186
1 vote
67 views

### Kyber implementation possible overflow in the NTT subroutine?

I took a look at the code from Kyber, which I would like to quote here: ...
• 413
76 views

### How can LCG based stream ciphers be broken?

I'm watching Christoph Paar's Introduction to Cryptography lecture series on youtube. In it he describes an example of an insecure stream cipher which uses XOR as the encryption and decryption ...
• 111
39 views

### Constraints needed to express a + b + c = d in zkp circuit

I am writing an ECC based zkp circuit and need to express the constraints: a + b + c = d a, b, c, d >= 0 a, b, c, d will be represented by points on the curve so addition can wrap around the ...
• 101
74 views

• 111
98 views

### Properties of Sums of Legendre Symbols

Context An unknown modulus N with 8 unknown prime factors $p_1, p_2, p_3, p_4, p_5, p_6, p_7, p_8$ a plaintext $m$ is encrypted with the formula $c = 2^m \mod N$ the only things the attacker know are ...
46 views

### Speedups for non-constant time modular arithmetic?

I am interested in modular arithmetic with respect to the prime $p = 2^{64}-2^{32}+1$. Thomas Pornin has some work on constant time implementation of arithmetic in $\mathsf{GF}(p)$ for this prime (the ...
• 13.5k
1 vote
151 views

### Solving equation of xor and mod operation

How do I solve equations like this $$(aX \oplus X+b) \bmod M = c$$ If a,b and c are known? and if i have system of of equation with different b values, is it solvable? I am particularly interested in ...
• 11
1 vote
100 views

### Finding two inputs [i, j] of a custom Hash function where their Hashes are [H(i), H(j)] = [H(i), H(i)^2] [closed]

I came upon the following hash function (pseudo-code): ...
• 33
1 vote
166 views

• 11
360 views

### Efficient multiplication modulo a square

Can anyone point me to techniques for efficient computation of modular multiplication/exponentiation modulo a square, as comes up, e.g., in the context of Paillier encryption? The standard references ...
• 305
1 vote
85 views

• 113
189 views

### Trouble detecting cyclic group order crossovers in SECP256K1

There's a problem in detecting whether the sum of public key addition has crossed the cyclic group order boundary For this example, think of public keys $Pub$ as private keys $Priv$, (private scalars),...
628 views

### Reverse engineering hardware crypto processor for modular multiplication

I'm currently working with an undocumented crypto offload processor that is capable of accelerating modular multiplication in some fashion. I need to figure out what operation it is implementing ...
• 53
32 views

### Cryptographic Applications of Composite Modular Exponentiation

I've developed an algorithm for fast modular exponentiation modulo composite numbers with known factorization. I'm not very well versed in cryptography, so I'm wondering if any of you know of an ...
1k views

### Concrete example of Montgomery Multiplication

I have read about Montgomery Multiplication on several sites, but I haven't found any examples on specific numbers that explain the algorithm to someone who doesn't have a PhD in number theory. I know ...
1 vote
106 views

### Findings solutions to a modular equation within specified intervals

What are some approaches to find (ideally many/all) pairs of numbers $(x, y)$ with $x \in [x_{\text{low}}, x_{\text{high}}]$ and $y \in [y_{\text{low}}, y_{\text{high}}]$ such that the following ...
• 13
1 vote
183 views

### modular reduction using solinas prime

I want to perform a modular reduction using Solinas prime value as q = 2^383-2^33+1. How can I efficiently compute it taking advantage of q being Solinas prime?
• 11
181 views

### Parameters needed for Chaum-Pedersen Protocol

I've came across a Stackexchange question about the Chaum-Pedersen Protocol which is based on the generalised schnorr protocol. As I understand it, it uses discrete logs and cyclic groups of prime ...
1 vote
304 views

### State recovery algorithm for Xorshift128 given modular outputs

I am researching the Xorshift128 PRNG. I am particularly interested in recovering the state given a set of outputs that have the remainder taken with different values. A common way to take a unsigned ...
210 views

### Why isn't the provided scheme UF-CMA secure?

On an exam I recently took, one of the questions was: Consider the following signature scheme. The public key is $(p,g,g^x)$, where $p$ is a large prime number. $g$ is a generator of $\mathbb Z^*_p$, ...
• 23
134 views

### Novice Question: Rivest Shamir Wagner 96 Time Lock Puzzles

I'm using the Rivest Shamir Wagner Time Lock Puzzle setup in an application, leveraging Pietrzak's algorithm for generating the proof. My question has to do with selecting a proper starting point. ...
• 131
45 views

### Security of modular exponentiation for non-uniform inputs

Suppose we have a function $F = f_{s}(x)$ with a key $s \gets \mathbb{Z}_q$ that on input $x$ outputs modular exponentiation $x^s$, where $\mathbb{G}$ is a cyclic group of order $q$ where DDH is hard. ...
• 558
905 views

### CRYSTALS-Dilithium - How do the supporting algorithms work?

I am studying the Dilithium signature from Ducas et al's CRYSTALS-Dilithium: A Lattice-Based Digital Signature Scheme. Wanting to understand how the supporting algorithms work together, I am trying ...
• 335
So there’s LadderLeak. RFC6979 produces uniformly random nonce $k$. There are other techniques, such as hash-to-curve standard (draft-irtf-cfrg-hash-to-curve-16 section 5), which allows to produce ...