Questions tagged [modular-arithmetic]
Modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" upon reaching a certain value… the modulus.
288
questions
0
votes
1answer
46 views
Get points of an Elliptic Curve defined over a Finite Field on Twisted Edwards Extended Coordinates
I'm working on a crypto library, and I need to perform some tests for the implementation of:
Point Addition.
Point Subtraction.
Point Doubling.
Scalar Mul Point.
The operations are performed on ...
-1
votes
0answers
42 views
Structure of $\mathbb{Z}/N^3\mathbb{Z}$
Let $N=pq$.
For $z\in\mathbb{Z}/N^2\mathbb{Z}$ we have the decomposition result under the form :
$z=(1+N)^xy^N$ where $x\in\mathbb{Z}/N\mathbb{Z}$, $y\in\left(\mathbb{Z}/N\mathbb{Z}\right)^*$.
Do ...
2
votes
4answers
296 views
How to use “mod” related words in technical paper？
Modular reduction is a widely used arithmetic operation. I found many "mod" related words such as
modulo
modulus
modular
Can anyone explains the difference among these words? Please give examples ...
3
votes
0answers
76 views
What can be said about the self-power map on groups based on DLP?
Introduction
I've been playing with group representation theory some time, concretely representing groups as permutation groups (Cayley's theorem), where the group $G$ has an embedding into the ...
0
votes
1answer
40 views
Probabilistic verification of signature schemes like RSA?
I was wondering if there were any verification algorithm in the literature that enables a "probabilistic" verification of well-known signature schemes?
For RSA signature verification for example, is ...
0
votes
2answers
39 views
Discrepancy in modular encryption
I'm trying to work through an encryption assignment and the instructions aren't particularly clear because they don't go hand in hand with the lecture video.
Using encryption key e = 9 in modulo 23,...
4
votes
1answer
78 views
What makes the quadratic residuosity problem hard?
The quadratic residuosity problem is the problem of determining whether, for given $r$, $m$, $\exists a.a^2\equiv r\mod m$.
This problem's believed to be hard to solve in general (e.g. an efficient ...
1
vote
1answer
94 views
Small solutions to modular arithmetic linear congruence
Let $p$ be a prime number with $N$ bits, let $a,b,c$ be constants. The problem is to find solutions to the equivalent $a x + b y \equiv c \pmod p$ with both having at most $N/2$ bits.
What ...
-1
votes
1answer
61 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 ...
0
votes
1answer
38 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?
...
0
votes
1answer
83 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 ...
3
votes
0answers
53 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{...
1
vote
0answers
37 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 ...
0
votes
1answer
56 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=...
2
votes
1answer
147 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,(\...
0
votes
1answer
107 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()):
...
4
votes
1answer
108 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 - ...
0
votes
1answer
43 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 ...
4
votes
1answer
379 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 ...
1
vote
1answer
168 views
Factoring RSA weak modulus
Given a public key for RSA, I have extracted the modulus which looks like this :
...
0
votes
0answers
35 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 ...
1
vote
1answer
70 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$, ...
1
vote
0answers
131 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?
3
votes
1answer
253 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 ...
2
votes
0answers
61 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 ...
1
vote
1answer
94 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
87 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
101 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 ...
2
votes
2answers
208 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
136 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
39 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
57 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$
6
votes
3answers
118 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
120 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
102 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
155 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
100 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
70 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
171 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} . ...
2
votes
2answers
78 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
50 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
262 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
49 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
134 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
58 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
64 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
45 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
134 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
79 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 ...
