Questions tagged [modular-arithmetic]
Modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" upon reaching a certain value… the modulus.
318
questions
1
vote
1answer
29 views
How to solve polynomial modular equation to create a correct decryption algorithm
I recently had a variant of the following problem in my cryptography course and I had trouble solving it and was looking to get some help.
Given the symmetric key cryptosystem: $\text{KG, Enc, Dec}$ ...
3
votes
1answer
86 views
Constructing an integer with specific totient without factorization
Given $N(=pq)$, but not its factorization. Somehow you manage to know, that $k$ divides $\phi(N)$. Is it possible to come up with an integer $N^{*}$, for which $\phi(N^{*})=\phi(N)/k$, without ...
2
votes
1answer
104 views
How to find the inverse of a polynomial in NTRU-PKCS
I am coding a java based implementation of the NTRU public-key cryptosystem. I can comprehend the majority of the algorithms involved in the encryption and decryption process well enough, but the key ...
0
votes
1answer
63 views
Are bijective polynomials of degree $2 \bmod 2^m$ efficiently inverted?
Take a bijective polynomial of degree $2 \bmod 2^{64}$ like:
$m = (n(n+1)/2)\ \bmod 2^{64}$
It is bijective and can trivially be inverted for numbers up to $2^{32}$ by calculating $\lfloor\sqrt{2m}\...
1
vote
1answer
37 views
Lai-Massey scheme
One rationale for Lai-Massey design is to achieve full diffusion in a single round compared to SPN and Feistel (hence less rounds number) due to use of multiplication-addition (MA) function. However ...
1
vote
1answer
31 views
Is there a quick method of listing certain elements of a cyclic group?
I'm studying applied cryptography and stumbled upon the following question to practice the knowledge about Congruence, Groups etc.
"List all Elements $x$, where $x^2 = 2$ in $\mathbb{Z}_{31}$
Okay, ...
0
votes
1answer
87 views
Exponentiating big numbers for RSA operation
I am following the book "Network security private communication in a public world - 2nd edition. Section 6.3.4.1 Exponentiating big numbers.
base = 123, exponent = 54, mod = 678
What I understand is ...
1
vote
1answer
92 views
Given generator $g$ with prime order $k$ in $\bmod P$. Does increasing $P = 2 \cdot c \cdot k +1$ decrease security? Increasing $g$ increase security?
An adversary wants to find $a$ in
$$m \equiv g^a \bmod P$$
He knows prime $P = 2 \cdot c \cdot k +1$ with it's primes $c,k$, value $m$ and $g$. And he also knows that $g$ only has an order of $k$, ...
3
votes
1answer
96 views
Is the member sum of a subset of $\mathbb{Z}/p\mathbb{Z}$ known (with $g^n \bmod p$)? Is it always $\mod P = 0$?
Let $P$ be a prime and $g$ a value between $2$ and $P$.
Let $M$ be the set of numbers which can be generated with $g$:
$$M = \{g^n\bmod P, \text{ with } 0 < n <P \}$$
If $g$ is a prime root of $...
1
vote
2answers
81 views
Extracting modulus from hidden function
I have a hidden function $f(x) = x \pmod{n}$ and would like to solve for $n$ based on a set of input and output pairs which can be chosen freely.
I would like to do this without brute force (i.e. ...
2
votes
1answer
102 views
Finding a pair of exponents so that $c^a \bmod N = c^b \bmod N$
I am not very familiar with RSA, so this question may appear to be stupid.
Suppose that in RSA encryption, we are given $c$ (the ciphertext) and $N$ (the semi-prime modulus), can we find a pair of ...
0
votes
1answer
51 views
In RSA encryption, can I calculate d given only m,n,c and e? [duplicate]
Newbie here. Not familiar with cryptography; just interested and reading up about it from time to time.
We know that the RSA problem (let's say $c=m^e \bmod N, c^d= m \bmod N$) is about recovering $...
0
votes
1answer
49 views
Understanding simplification steps when solving complicated equations in Galois Field
I just encountered a problem when I tried to understand a basepoint conversion from x25519 to ed25519. I can't really wrap my head around how the value of $x$ can be the stated value below? Can ...
1
vote
1answer
137 views
Discrete Logarithm: Given a p, what does it mean to find the discrete logarithm of x to base y?
My understanding is that $a^b \bmod p$ is the discrete logarithm problem. Given the question is worded this way, are we trying to find $ \log_y x \bmod p$.
For instance, if we are trying to compute ...
3
votes
1answer
87 views
Is it possible to construct a multiplicative group from $\mathbb{Z}_n$ if $n$ is not a prime number?
With $n$ being a prime number I know we can generate groups over multiplication. Is it possible the other way around ($n$ not being a prime)?
2
votes
1answer
106 views
Index Calculus for Discrete Logarithm
I'm studying the Index Calculus method for Discrete Logarithm. In the book "Introduction to Cryptography with Coding Theory" by Trappe it's told that, if $$\alpha^k\equiv \prod p_i^{a^i} \mod p$$ ...
0
votes
1answer
53 views
Why does using a prime-order subgroup in DLP improve security?
Let's consider a discrete logarithm
$\beta \equiv \alpha ^{x} \bmod \,\, p$
We can solve it using Pohlig-Hellman algorithm. And, if $p-1 = tq$ where $q$ is a large prime factor, we can avoid any ...
2
votes
1answer
90 views
Weakness in Pohlig-Hellman algorithm
Let's try to solve a discrete logarithm:
$\beta \equiv \alpha ^{x} \bmod \,\, p$
using the Pohlig-Hellman algorithm. Let's suppose that $p-1=tq$, where $q$ is a large prime number. This means that ...
0
votes
0answers
27 views
Given a deterministic oracle that calculates square roots modulo n, factor n
When $n = pq$ where $p$ and $q$ are primes, we can generate random numbers until we get $a$ and $b$ such that $a^2 \equiv b^2 \pmod n$. This implies $n$ has some common factor with $a^2-b^2$, and then ...
0
votes
1answer
58 views
Explaining modulo reduction of curve25519, multiply hi bits with 38 trick?
I have learnt that there is a trick where you can speed up the reduction modulo of a point (x-value) in a x25519 curve. Since, it uses the prime number $2^{255} - 19$.
From article:
Reduction ...
1
vote
2answers
70 views
Meaning of “integers modulo 4 ” in “Fully homomorphic encryption modulo Fermat numbers” scheme
My question refers to the paper "Fully homomorphic encryption modulo
Fermat numbers" by Antoine Joux. On page 3, the author describes a basic concept of the system:
As many FHE systems, we deal ...
1
vote
0answers
50 views
What is the state of the art in fast implementation techniques for modular exponentiation?
I want to calculate ($m^{e} \pmod{N}$) in C or C++. I want to use 2048 bits long modulus $N$ and thus the above process of ...
0
votes
2answers
184 views
Efficient function/algorithm/method to do modular exponentiation
I was working on this project where I needed an RSA key, and I wondered if there was and more efficient way of doing $g^a \bmod n$ other than calculating $g^a$ and then finding the remainder when you ...
0
votes
1answer
78 views
How to represent the point-at-infinity(Elliptic Curves) in code? [duplicate]
I am writing code for Elliptic Curve Cryptography. I have a class class EllipticCurvePoint.
...
3
votes
2answers
341 views
Why is RSA encryption performed in mod n, but computation of inverse in $\bmod \varphi(n)$
I am studying the principles of RSA and have come across some unintuitive statements. Lets revisit the RSA algorithm:
RSA Key Generation
Output: public key: $k_{pub} = (n,e)$ and private key: $k_{pr}...
0
votes
0answers
34 views
GCD in Montgomery arithmetic
Wikipedia article on Montgomery modular multiplication contains the following statement:
Many operations of interest modulo $N$ can be expressed equally well in Montgomery form. Addition, ...
1
vote
2answers
65 views
RSA-CRT exponent reduction
In the implementation of RSA-CRT, the exponent d is reduced mod p-1 ($d_p = d \bmod {(p-1)}$). The only proof I've found for that, is the following (considering $d = k\varphi(p) + d \bmod {\varphi(p)}$...
1
vote
0answers
47 views
EC threshold private key's multiplicative inverse and derived-key sharing
I have two devices, and each has a private key xPriv-i. Each device computes the corresponding EC public key xPub-i, shares it, and the linear combination of the keys is the "real" public key xPub. ...
0
votes
1answer
52 views
Relationship between special RSA modulus and quadratic residue in CL (Camenisch-Lysyanskaya) signature
I'm studying the CL(Camenisch-Lysyanskaya) signature (A signature scheme with efficient protocol proposed by Camenisch-Lysyanskaya).
However, I cannot understand ...
0
votes
1answer
66 views
structure in modular arithmetic
I was playing around with modular arithmetic when I noticed something.
\begin{align}
g^k &= a \bmod n\\
g^{k+0.5(n-1)} &= b \bmod n
\end{align}
Then $a + b = n$, so you can also write
$$g^{...
1
vote
1answer
148 views
Hill Cipher Plaintext Attack: Dealing with Non-uniqueness of Matrix Inverses?
I'm following along with my book. Here is an example of a plaintext attack from it:
It is known that:
plaintext = 'friday'
ciphertext= 'pqcfku'
$m$ = 2
We will use this to form the following matrix ...
0
votes
1answer
80 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 ...
2
votes
4answers
319 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
1answer
135 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 ...
1
vote
1answer
79 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
58 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
143 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
149 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
91 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
66 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
124 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
61 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
41 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
63 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
325 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
202 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
288 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
60 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
420 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 ...
2
votes
1answer
295 views
Factoring RSA weak modulus
Given a public key for RSA, I have extracted the modulus which looks like this :
...
