Questions tagged [modular-arithmetic]

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

Filter by
Sorted by
Tagged with
0 votes
1 answer
415 views

Is modular exponentiation always cyclical?

In RSA clock arithmetics is used, and as Fermat's little theorem says, $a^p \bmod p = a$. The exponentiation is cyclical, $a^x = a^{x \bmod p-1} \bmod p$, the same sequence of numbers is repeated in ...
mimesis's user avatar
  • 13
1 vote
1 answer
314 views

Question about using Montgomery form for elliptic curve operations on bls12-381

Since the prime for bls12-381 is not of a form to allow easy modular reduction , is the best approach to use the Montgomery multiplication + reduction algorithm? ...
bsdevlin's user avatar
1 vote
1 answer
697 views

What makes the Discrete Logarithm Problem hard?

I am missing a crucial piece of the maths behind the DLP, and I'm hoping someone can give me a really dumbed down answer.. If $h=g^x \bmod p$ and we're working in the group $Z^*_p$, why can I not ...
Jamal Rahman's user avatar
3 votes
0 answers
72 views

Problem with Chaum`s Untraceable Electronic Cash

For example according to protocol I need calculate this: $b=F^{(1/h)} \bmod pq.$ Where $p$ and $q$ are prime numbers. I have $F$ and $h$. But how can I calculate $b$? I tried to do this: $\text{...
mariyah's user avatar
  • 31
1 vote
0 answers
55 views

Efficient fields over arithmetic circuits

What sort of fields is efficient over an arithmetic circuit? Efficient meaning that given a field $\mathbb{F}_p$, reduction (modulo) does not require many multiplications and preferably inversion was ...
WeCanBeFriends's user avatar
0 votes
1 answer
142 views

Finding a base of an exponent in mod field

I have the following equation: $$base^{exp} = number \pmod n : base,exp \in \mathbb{N}$$ and another known fact is: $$gcd(base, number) = 1$$ $$n = 2^{2048}$$ base=...
Guy Sudai's user avatar
  • 125
2 votes
1 answer
1k views

find $a$ and $k$ for a given el gamal cryptosystem

I am given this question: Suppose Alice is using the ElGamal Signature scheme with parameters $p = 31847$, $\alpha = 5$, and $\beta = 25703$ Assuming that we have received signed messages $(x_1,(\...
wade king's user avatar
  • 131
1 vote
1 answer
521 views

How does the squeeze function in the NaCl Poly1305 implementation work?

The NaCl ref implementation of the Poly1305 algorithm uses the following reduction function (which is called squeeze()): ...
Peter's user avatar
  • 113
4 votes
1 answer
1k views

How can I exploit the structure of the secp256k1 prime for fast arithmetic?

I'm implementing logic on an FPGA (programmable chip) that does the key verification part of ECDSA on the curve secpk256k1, in which all operations are mod p where $p = 2^{256} - 2^{32} - 2^9 - 2^8 - ...
bsdevlin's user avatar
0 votes
1 answer
100 views

Additive Differential of XOR

I'm studying about Additive differential of XOR I saw two papers that are "H.Lipmaa et al., On the Additive Differential Probability of Exclusive-or" and "V.Velichkov et al., The Additive ...
jyj's user avatar
  • 129
4 votes
1 answer
471 views

Salsa20 Implementation: Sum of 2 Words with Carries Suppressed

I'm working on the 2nd part of the Salsa20 spec, and I want to implement a closure for the exclusive-or of two words(u32). The author defines the operation as the sum of two words with carries ...
whole_lotta_coins's user avatar
2 votes
1 answer
922 views

Factoring RSA weak modulus

Given a public key for RSA, I have extracted the modulus which looks like this : ...
Mzem's user avatar
  • 75
0 votes
0 answers
56 views

Speeding up quotient determination in high-radix montgomery modular multiplication

In this paper Simplifying Quotient Determination in High-Radix Modular Multiplication, the authors have proposed to replace the original modulus $M$ in Montgomery Multiplication $ABR^{-1} \bmod{M}$ to ...
mksit's user avatar
  • 1
1 vote
1 answer
85 views

$m^b = z^b \pmod{n}$ - single solution $m = z$?

If i have the following equation: $$m^b = z^b \pmod{n}$$ Where all numbers are taken from the multiplicative group $\mathbb{Z}_n^*$. Suppose I know the values $z$ and $b$. Can I state that $z = m$, ...
caffein's user avatar
  • 223
1 vote
0 answers
530 views

Finding generator element for multiplicative group of order $n$ - feasible?

Given a multiplicative group of order $n$, how hard is it to find a generator element (such that all other elements can be expressed as powers of that generator)? What would be the complexity?
caffein's user avatar
  • 223
3 votes
1 answer
1k views

Diffie-Hellman private key recover with non-prime modulus

Say we have a classic Diffie-Hellman key exchange. We have the following parameters of a public key: p,g,y Where $p$ is the modulus, $g$ is the base, $y$ is the ...
Not J. Doe's user avatar
2 votes
0 answers
104 views

Hamming Weight of Solutions to the Frobenius Equation

My area of research is algorithms for calculating optimal addition chains. I have a new high performance algorithm that at its core benefits from estimating the number of set bits ($v(n)$ Hamming ...
Neill Clift's user avatar
1 vote
1 answer
278 views

Diffie hellman: fixed modulus a risk?

In DH, are algorithms with fixed modulus p (large safe prime) to be avoided? What if it was changed every x minutes?
Kroma's user avatar
  • 235
1 vote
1 answer
353 views

What is the difference between subtracting the modulus from a scalar field element and reducing it?

When implementing a Field element, we define the necessary operations on the data structure. One function that I see is a "scalar reduce" function, which effectively reduces a random scalar so that ...
WeCanBeFriends's user avatar
-1 votes
1 answer
2k views

find additive inverse of modular arithmetic [closed]

For a set to be called as a ring, it should have the following properties closed commutative associative Identity existence Inverse existence but how is Z7 a ring, as there aren't any inverse ...
PDHide's user avatar
  • 247
2 votes
2 answers
2k views

What prevents the successful use of the Giant-step/Baby-step algorithm solving a discrete log problem implemented with modulo arithmetic?

Does the size of base, exponent, and modulus thwart the Giant-step/Baby-step algorithm in solving DLP using modular arithmetic or is it the use of a property of a particular prime as the modulus, or ...
JohnGalt's user avatar
  • 546
1 vote
1 answer
2k views

Determine RSA modulus from encryption oracle

Suppose we have an RSA encryption oracle $E(m)$ which basically just calculates $m^e \mod n$ for a given message $m$. Here $e=65537$ is known but $n$ is not. Can we determine the value of $n$ without ...
Jannes Braet's user avatar
0 votes
1 answer
47 views

Can we find the exact number given remainder of the numbers with mod m?

I have around 1500 numbers. The numbers $x_i$ are calculated as $x_i$=($p*t_i$) mod m. $p$ constant and same for all the numbers while $t_i$ are chosen randomly everytime. For example the given ...
Ram_Giri's user avatar
0 votes
1 answer
164 views

Collisions in Diffie-Hellman private keys

Given a generator $g$, a large, safe prime $P$ and a result of the DH key exchange $g^{xy} \mod P$, how would I come up with two different $x', y'$ s.t. $g^{x'y'} = g^{xy} \mod P$
dc3cdd1fc7's user avatar
6 votes
3 answers
468 views

Mixing x into permutation through XOR vs. modular addition

Block ciphers mix key material into the permutation through XOR. Also do pre and post whitening this way. Chacha/Salsa finishes by 32-bit modular adding key and iv material (among other bits but ...
user avatar
-1 votes
3 answers
140 views

In modular arithmetic, why is $\left(g^{k_1} \bmod n\right)^{k_2} \bmod n = \left(g^{k_1}\right)^{k_2} \bmod n$? [duplicate]

Why is $\left(g^{k_1} \bmod n\right)^{k_2} \bmod n = \left(g^{k_1}\right)^{k_2} \bmod n$ ? Note of the editor: I used $=$ where the original question used == because $=$ in a cryptographic context is ...
dhk's user avatar
  • 39
0 votes
4 answers
248 views

Diffie-Hellman key exchange: Why is $(g^{k_1} \bmod n )^{k_2} \bmod n \equiv (g^{k_2} \mod n)^{k_1} \bmod n$

In a Diffie-Hellman key exchange, with a generator $g$ and a modulo $n$, and two keys $k_1$ and $k_2$, why is $(g^{k_1} \bmod n )^{k_2} \bmod n \equiv (g^{k_2} \mod n)^{k_1} \bmod n$
dhk's user avatar
  • 39
7 votes
2 answers
3k views

How to avoid side channel attacks when handling large numbers?

For cryptography, the platforms have limited size as 32 or 64-bit operations. We definitely need big numbers to implement the encryption/decryption and digital signatures for cryptosystems like RSA, ...
kelalaka's user avatar
  • 48.5k
7 votes
2 answers
491 views

Regular and Efficient doubling in $GF(2^n)$

A naive approach to compute a multiplication $a \cdot b$ in a Galois field of the form $GF(2^n)$ is the russian peasant algorithm. However, it does not run in constant time and therefore is not safe ...
Raoul722's user avatar
  • 2,836
3 votes
1 answer
419 views

Can modular multiplicative inverse be used to create a secure cipher?

Let $N$ be a large number; and $(e, d, N)$ be a secret-key; where $e$ is a one-time random factor, and large enough (say the more or less the same number of bits as $N$), where $e < N$ and $e * d \...
zetaprime's user avatar
  • 591
-5 votes
1 answer
376 views

One Time Pad OTP: with modular math, ciphertext reveals modulus always, yes or no?

Assuming that in the OTP scheme, the key has more values than the alphabet, then: using modular math predetermines that the highest possible value in the ciphertext will reveal the modulus used in ...
EncryptThis's user avatar
-2 votes
2 answers
639 views

One-Time Pad : How does modulus size greater than alphabet size eliminate perfect secrecy?

If my plaintext alphabet is {0,1,2} has three characters, I understand why I cannot use a modulus less than 3 (decryption won't work). My key has 100 different values, {0,1,2 .....99} . So key ...
EncryptThis's user avatar
2 votes
2 answers
166 views

One Time Pad OTP : Optimal modular base per given plaintext space?

Background: my question at : My pencil and paper One Time Pad works fine without modular math ...... or does it? I am trying to understand, from a layman's point of view, how to make the best one ...
EncryptThis's user avatar
2 votes
1 answer
135 views

choices for k in binary finite field modular reduction algorithm

In the Guide to Elliptic Curve Cryptography there's this algorithm: My question is... what is $k$? Is it just some random value we pick? If so are some numbers better than others?
neubert's user avatar
  • 2,927
4 votes
1 answer
404 views

RSA given d and d = p

Assume we have a somehow unorthodox implementation of RSA whereby: $p$ and $q$ are chosen primes of length $n/2$ where $n$ is the number of bits desired in $N=p\,q$ and $$\begin{align} \phi &= (p-...
S. L.'s user avatar
  • 421
1 vote
1 answer
75 views

Additive homomorphic encryption: strict equality - handling congruence

Is there an additive homomorphic encryption scheme which guarantees that if provided with $E(v)$, $E(m_1)$ and $E(m_2)$ and $E(v)=E(m_1).E(m_2)$ then $v=m_1+m_2$ Please note this is not $v \equiv ...
BGR's user avatar
  • 179
1 vote
2 answers
212 views

My pencil and paper One Time Pad works fine without modular math ...... or does it?

With no background in higher math or computer science, I could not quite grasp the value of modular math for simple OTP systems as described in other posts here. I have an alphabet size of 40 ...
EncryptThis's user avatar
2 votes
2 answers
123 views

Break large exponent calculation into smaller calculations?

I am implementing SRP on an embedded platform. It has crypto acceleration and I am using its built in modular exponentiation function, however it doesn't seem to be able to handle an exponent over 32 ...
uhsl_m's user avatar
  • 121
1 vote
1 answer
94 views

Computations in extended finite field p^2

I would like to construct a distortion map from a point $\in \mathbb{F}_p$ to $\mathbb{F}_{p^2}$. If I have an elliptic curve $Y^2 = X^3 + 1$ over $\mathbb{F}_p$ and a distortion map $\phi(x,y) \...
user1990088's user avatar
1 vote
0 answers
57 views

Geometry of the outputs of linear congruential random number generators

I learned that possible $m$ long sequences produced by linear congruential random number generators(of the form $r_{i+1}\equiv ar_i+b \mod n$) fall on hyperplanes. Using this fact I have come to think ...
JeWe37's user avatar
  • 11
4 votes
0 answers
161 views

Indistinguishability vs fixed bit-length

Suppose there is a cyclic group $\mathbb{G}$ of prime order $q$ of elements in $Z^{∗}_p$ with a generator $g$ and values $a,b,c,d \in Z_q$. There is also an equation $g^{ab} = g^{cd}$, where $a,b,c$ ...
pintor's user avatar
  • 558
0 votes
2 answers
129 views

Public-key generation - primes reuse

Given the following Trap-door Commitment scheme Secret key receiver: $x_B \in_u Z_q$ Public key receiver: $y_B = g^{x_B} \mod p$ Here, $p=q*k+1$ for two primes $p,q$ and $k \in Z$. And $g$ is the ...
Crypto Learner's user avatar
1 vote
1 answer
385 views

Paillier: guessing the message when knowing the cipher and the random number

I cannot get my head around this. In Paillier, the ciphertext is calculated using $c = g^m.r^n\ mod\ n^2$ where $(n,g)$ forms the public key and $r$ is a random number $0<r<n$. Assuming an ...
BGR's user avatar
  • 179
0 votes
2 answers
2k views

RSA: finding e given n, m and c

So I'm not sure if this is possible but assume I have $$c \equiv m^e \pmod n$$ I have $c$, $m$ and $n$ but no $e$, which in my case I a value that can be up to 15 digits. Is there a way to do this?
S. L.'s user avatar
  • 421
0 votes
1 answer
308 views

Is there a formula for calculating the inverse of a sum in modular arithmetic?

Suppose there is a cyclic group $G$ of prime order $q$ of elements in $Z_p^*$ with a generator $g$ and a value $x \in Z_q$. $h_1 = g^{x+1}$ $h_2 = g^{x}$ Is it possible to write $h_2^{((x+1)^{-1})}...
pintor's user avatar
  • 558
5 votes
1 answer
148 views

Why FHE takes modulo space $\Bbb Z_p$ as $[−p/2,p/2)$ rather than $[0,p)$?

Why doesn't FHE scheme see a modulus space $\Bbb Z_p$ as $[0,p)$ ? Instead, it consider $\Bbb Z_p$ as $\left[-\frac{p}{2},\frac{p}{2}\right)$. What's the concrete reason? What happens if I use $[0,p)$...
mallea's user avatar
  • 1,615
-1 votes
2 answers
318 views

A quick way to justify whether $a^m \equiv 1 \pmod{n}$?

Say I would like to justify whether $10^{28} \equiv 1 \pmod{29}$. I know according to Fermat's little theorem that $a^{p-1} \equiv 1 \pmod{p}$ when $a$ is a primitive root modulo $p$. What about ...
Mithun Ogawa's user avatar
4 votes
1 answer
3k views

Solving the discrete logarithm problem for a weak group

I was reading an answer about an attack on a weak group for the discrete logarithm problem and wanted to formalize and verify that the attack was correct. That is, that it was guaranteed to always ...
user avatar
2 votes
1 answer
538 views

Solve System of Equations including XOR and Modular Addition

A Dummy cipher is shown in figure below. Plaintext is 16 bits ($X_1$ and $X_2$ are 8 bit each). Ciphertext is computed after two rounds using two round keys $K_1$ and $K_2$. Can the round keys $K_1$ ...
crypt's user avatar
  • 2,427
4 votes
1 answer
1k views

How can I determine if a hash function is secure?

I'm doing an exam in computer security and I encountered this problem which I'm unsure of how to attack properly. Should I get down and dirty with the Hash function on paper or is there a more general ...
Mountain_sheep's user avatar

1
3 4
5
6 7
10