Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [modular-arithmetic]

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

1
vote
0answers
56 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?
1
vote
1answer
77 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 ...
-1
votes
1answer
36 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 ...
0
votes
0answers
52 views

Are the Baby-step/Giant-step, Pohlig–Hellman, Index Calculs, and NFS algorithms to compute a discrete log modulo n effective with a composite modulus?

I've read different posts about the effectiveness of Baby-step/Giant-step on computing DLP with a composite modulus. This one seems to indicate that Baby-step/Giant-step is for use with a prime ...
2
votes
2answers
104 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 ...
1
vote
1answer
79 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 ...
0
votes
1answer
36 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 ...
0
votes
1answer
34 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$
5
votes
3answers
89 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 ...
-1
votes
3answers
117 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 ...
0
votes
4answers
87 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$
8
votes
2answers
2k 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, ...
7
votes
2answers
147 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 ...
3
votes
1answer
84 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 \...
-5
votes
1answer
52 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 ...
-1
votes
2answers
130 views

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

If my plaintext alphabet is {0,1,2}, it has three characters, and 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} . ...
1
vote
2answers
65 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 ...
2
votes
1answer
43 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?
4
votes
1answer
233 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-...
1
vote
1answer
43 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 ...
1
vote
2answers
130 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 ...
2
votes
2answers
48 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 ...
1
vote
1answer
58 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) \...
1
vote
0answers
41 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 ...
4
votes
0answers
132 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$ ...
0
votes
2answers
71 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 ...
1
vote
1answer
329 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 ...
0
votes
2answers
129 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?
0
votes
1answer
73 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})}...
5
votes
1answer
106 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)$...
-1
votes
2answers
162 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 ...
4
votes
1answer
284 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 ...
0
votes
0answers
30 views

Remainder of two large boolean Arrays (length>1024 bit)

I'm fairly new to cryptographic topics. At the moment I am failing at a "simple" task: I want to compute $x \bmod n$ with x and n beeing Boolean Arrays (representing integers) with size greater than ...
0
votes
0answers
46 views

Constructing System of Equations of Modular Subtraction, Modular Multiplication and XORS

This is a toy cipher. The design is inspired by a question (Solve System of Equations including XOR and Modular Addition), however the design involves different operations. My cipher takes as input 2 ...
2
votes
1answer
108 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$ ...
4
votes
1answer
160 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 ...
2
votes
0answers
49 views

Algebraic Attack on Mix Mode Modular Arithmetic

I have a toy cipher that comprises of Mix Mode Modular Arithmetic (bit similar to IDEA including, Addition Modulo $2^{n}$ , Multiplication Modulo $2^{n}$ , Subtraction Modulo $2^{n}$ and circular ...
1
vote
1answer
43 views

Modifying Mix Mode Modular Arithmetic in IDEA Cipher

IDEA uses Mix Mode Modular Arithmetic that includes Addition Modulo $2^{16}$ and Multiplication Modulo $2^{16}+1$. If Multiplication Modulo with $2^{16}$ is used instead of $2^{16}+1$ (where $2^{16}$...
-2
votes
1answer
74 views

Security Implications of Multiplication Modulo with a composite

Cryptographic algorithms are designed using an irreducible polynomial. Irreducible polynomial generates entire field and multiplicative inverse of all elements (less zero) exist. A sample ...
0
votes
0answers
57 views

Finding $d$ in RSA Encryption mathematically and by hand

I'm working on this RSA encryption problem and the catch is that it must be done by hand and mathematically. Let's say $p=11$, $q=13$ $$N=p \cdot q=11 \cdot 13=143$$ I chose $e$ to be relatively ...
3
votes
1answer
29 views

Measure Strength of Mix Mode Modular Arithmetic based Confusion Layer

Strength of sboxes is generally measured by different properties eg non linearity, fixed points etc. If confusion is provided by Mixed Mode Modular Arithmetic (eg as in IDEA), how to measure the ...
1
vote
0answers
264 views

In zkSNARKS, does R1CS require every step of the calculation, or just statements which confirm the calculation was performed correctly?

I was attempting to figure out a way to implement the modulo operation as a set of gates in an Rank-1 Constraint System, detailed by Vitalik Buterin here However, it occurred to me that maybe we don'...
-1
votes
2answers
122 views

Number theory: efficient modular exponentiation [closed]

If: \begin{align} k &= a\cdot b\cdot c\\ k_m &= k \bmod m\\ a_m &= a \bmod m\\ b_m &= b \bmod m\\ c_m &= c \bmod m\\ \end{align} Then is $B^{k_m} \bmod N$ always equivalent to: ...
-1
votes
1answer
65 views

How to compute this equation $(g^k)^\alpha\bmod p$

I have a question about implementation. How is an operation like this implemented? $$(g^k)^\alpha\bmod p$$ With all $g$, $k$, and $\alpha$ being large numbers. The thing that I find tricky is that ...
-2
votes
1answer
90 views

How to understand asymmetric cryptography? [closed]

Everywhere in the lessons on asymmetric encryption explains the process of encryption and messaging, but I'm interested in the asymmetric encryption algorithms themselves. The only thing I have so far ...
1
vote
1answer
132 views

Linear Feedback shift register over integers

The Solina's paper Generalized Mersenne Numbers contains a Linear Feedback shift register I am not able to understand. Here it is: It is supposed to be a normal Linear Feedback shift register but it ...
0
votes
0answers
39 views

Comparing computational costs of modular multiplication against an elgamal encryption?

I've been looking for a comparison program measure of various encryption schemes relative to individual operations used by the different schemes. I am having trouble finding one. What would be the ...
1
vote
1answer
341 views

Coppersmith's method implementation

suppose i have two equations: $$ (m)^{3} \bmod n = c_{0}$$ $$(m + 2^{k}r + d) \bmod n = c_{1}$$ The values($c_{0}, c_{1}, k, d$) are known. I wanted to retrieve r (ofc $|r| < n^{\frac{1}{9}})$ ...
1
vote
0answers
109 views

RSA high bits padding atack

Can we use Coppersmith's attack if we know a few ciphertexts of the same plaintext, but there is a short random bit padding in front of message? Formula: $$(2^k \cdot r + m)^3 \bmod n = c$$
0
votes
1answer
54 views

A file chunk in a group/field

I am reading a paper by Shacham and Waters on Compact Proofs of Retrievability. In this paper on page number 3 under section 1.1 in the very first line the author states that an encoded file is broken ...