Questions tagged [modular-arithmetic]
Modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" upon reaching a certain value… the modulus.
459
questions
0
votes
0
answers
3
views
Alphabet Substitution Cipher
The cipher is
AFGYogkyjuroxronglojkxo
Hints:
Alice said Adobe was attacked this year, find the sum of digits of that year. (Alice - a++)
Bob said i would want to know the month as well, i'm ...
0
votes
1
answer
66
views
Trying to understand the basic principle of RSA from Wikipedia
Quote from https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Operation
A basic principle behind RSA is the observation that it is practical
to find three very large positive integers $e$, $d$, and $n$,...
- 103
1
vote
1
answer
97
views
RSA: in $E(x) \equiv x^e \pmod N$, do we apply the mod function to $x^e$?
When one is computing $E(x) \equiv x^e \pmod N$ (where $N = pq$) in RSA, what is the precedent for which number in the residue class of $x^e$ to have as the result of this computation? Does this mean ...
- 123
2
votes
1
answer
92
views
How secure is this modified RSA (SRA / Mental Poker) algorithm?
I'm making a peer-to-peer game client using an already existing protocol where messages are broadcasted to all people on the network, and messages are already proven to be from a given user. One of ...
1
vote
2
answers
61
views
RSA: does it matter that we recover something congruent to x rather than equal to it?
In the proof that RSA successfully decrypts the message $x$, we show that $x^{e^{d}}\equiv x \pmod N$. However, I am wondering whether it is a problem that we don't recover $x$ exactly, but merely a ...
- 123
1
vote
2
answers
65
views
Question on Number Theoretic Transformation (NTT) Condition
For the NTT I know the following preconditions, which must be fulfilled for the primitive $N$-th root of unity:
$$ \omega^N \equiv 1 $$
$$ \sum_{i=0}^{N-1} \omega^{ik} \equiv 0 \quad k=1,\ldots,N-1 $$
...
- 85
0
votes
0
answers
34
views
Implementation of Ring Signature
I have implemented a ring signature in a Python program, To keep it simple, I have Alice and Bob. Based on this ring equation:
$$ v = E_k(y_s⊕E_k(y_i⊕v))$$
I will get:
$$ y_s = E_k^{-1}(v)⊕E_k(y_i⊕v) \...
- 11
6
votes
2
answers
335
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 ...
- 270
0
votes
1
answer
31
views
Asymptotic efficiency of modular multiplication
What is the best known asymptotic/concrete complexity of modular multiplication?
Using Montgomery multiplication, if $M(n)$ is the cost of one integer multiplication of $n$ bits, then the cost is $2M(...
- 1,065
1
vote
1
answer
305
views
Is this proof of RSA's correctness sufficient?
In a lecture at my university, the following proof of correctness of RSA is given (the lecture is not mainly on cryptography or even computer science):
$m^{ed} \equiv m^{ee^{-1}} \equiv m^{1} \equiv m ...
- 113
0
votes
0
answers
59
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),...
5
votes
1
answer
586
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
0
votes
0
answers
29
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 ...
- 113
2
votes
1
answer
246
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 ...
- 129
1
vote
2
answers
84
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
1
answer
94
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
2
votes
1
answer
65
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 ...
- 21
1
vote
2
answers
139
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 ...
- 11
2
votes
1
answer
82
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
3
votes
1
answer
103
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
1
vote
0
answers
42
views
A ctf practice question [closed]
Ciphertext : UCOWgokwyaqgkqguowgykkg
Alice said Adobe was attacked this year, find the sum of digits of that year. (Alice - a)
Bob said i would want to know the month as well, i'm curious. (Bob - b)
...
- 11
3
votes
1
answer
38
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. ...
- 528
3
votes
1
answer
377
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 ...
- 315
2
votes
1
answer
149
views
What degree of k bias is acceptable in ECDSA?
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 ...
- 300
1
vote
0
answers
31
views
How does the Mongomery Algorithm work? [closed]
can someone please explain to me what's the role of montgomery reduction algorithm and how to implement it in python. I wrote the code below to calculate a*b mod m but it doesn't seem to work well.
...
- 11
1
vote
1
answer
93
views
Z superscript confusion
I was practicing some questions on cryptography (newbie) and came across this question:
I know that Z26 means modulo-n arithmetic is used, but what does the superscript (3) denote? My guess is that ...
- 13
1
vote
1
answer
156
views
Using roots of unity mod n to break rsa when e and phi are not coprime
I am trying to solve an rsa problem where we only know the public key (n,e) and the ciphertext c.
The modulus n is actually a prime number, so we can easily compute phi as phi = n-1.
But the problem ...
- 23
3
votes
1
answer
203
views
How to decrypt c when e is not co-prime with phi(n) and e is non-prime
In RSA, I want to know a way to be able to retrieve all possible plaintexts $m$ given a ciphertext $c$, $\phi(n)$, $n$ and $e$. The decryption exponent $d$ can not be generated due to the fact that $e$...
- 31
2
votes
1
answer
95
views
Modulus for reduction in BLS Signature Scheme
I'm currently working with BLS Signature Schemes in the field of publicly verifiable Compact Proofs of Retrievability by Shacham and Waters.
So for creating the Sigmas the following function is ...
- 75
1
vote
1
answer
78
views
zk-SNARK: Encrypted Polynomial
I've read through, and roughly understand, Maksym Petkus' zk-SNARK paper (http://www.petkus.info/papers/WhyAndHowZkSnarkWorks.pdf). I'm re-reading it, and trying to code up the examples as I go along ...
- 13
6
votes
2
answers
1k
views
Must RSA exponent and modulus be odd
I'm working on some RSA code that uses Toms Fast Math (TFM for short), and I'm trying to understand why the functions fp_exptmod (for modular exponentiation ...
- 217
3
votes
2
answers
379
views
Why the polynomial of GCM is primitive?
I'm interested on the polynomial used in GCM-mode : $X^{128}+X^7+X^2+X+1$
This polynomial is Primitive (in $\mathbb{F}_2$).
What is the interest of choosing a primitive polynomial and not a simple ...
- 2,554
1
vote
1
answer
158
views
1
vote
0
answers
50
views
Compact Proofs of Retrievability publicly verifiable with RSA
I'm currently trying to implement compact proofs of retrievability that are publicly verifiable by RSA as described in this paper Compact Proofs of Retrievability in GO. I'm currently struggling on ...
- 75
1
vote
0
answers
48
views
Deal with large number
I'm having a problem in a RSA challenge. I already had p, and q is calculated based on p.
(100000000**(p-1) -1)%p
q is the nearest prime to this number.
I knew ...
- 11
0
votes
0
answers
66
views
Finding small roots of a univariate polynomial modulo N. Don Coppersmith
I'm currently trying to understand the Coppersmith's method of finding small integer roots of polynomials modulo some integer. I am reading the original paper Small Solutions to Polynomial Equations, ...
- 21
1
vote
1
answer
86
views
FHE modular reduction in specific range
I'm trying to implement a naive version of CKKS in Python.
It was great until I start implementing the modulus.
For this kind of schemes, the modulus $q$ is in the range $(-q/2,q/2]$.
How does this ...
- 21
1
vote
0
answers
70
views
How to solve a system of modular equations with exponential difference
I`m solving one crypto problem on rsa.
p^e - q^e = C1 (mod n)
(p-q)^e = C2 (mod n)
n = p*q*r; p,q,r are prime numbers
e = 2 * 65537
We have e, n, C1, C2.
It's ...
- 11
1
vote
1
answer
73
views
Constructing a straight line from two points not working in integer modulo group
I have a pair of coordinates of which all values belong to $Z_{p}$ where $p$ is a prime. I want to construct a straight line that goes through those two coordinates. Then I want to generate two more ...
- 153
0
votes
0
answers
112
views
How to get dp and dq of CRT-RSA?
I am learning to utilize flush+reload method to get private key of CRT-RSA.
CRT-RSA calculates two parts separately: mp = c^dp mod p and ...
- 101
0
votes
1
answer
65
views
Modular hashing confusion
I am trying to learn about basic hashing using the modulo operator and am a bit confused. In the text that I am reading, it says that the modulo operator can be used to accept an input of any length ...
- 3
0
votes
1
answer
50
views
MITM against NTRU
In MITM attacks against the NTRU cryptosystem, we exploit the fact that in the ring of truncated polynomials of degree $n-1$ it holds that $$fg=h\mod q$$ for our secret and public keys $f,h$. The ...
0
votes
1
answer
114
views
Can we force a chosen ciphertext to be decrypted to a chosen plaintext while controlling only $e(=3)$ in RSA? [duplicate]
I have bumped into this challenge from a well known CTF site. I don't want to make a reference to it because I don't want this to be a hint for anyone. And also to avoid giving out the source code of ...
- 848
3
votes
0
answers
126
views
Can reinforcement learning speed up modular multiplication?
In Discovering faster matrix multiplication algorithms with reinforcement learning (Nature, 2022; lightweight intro), the authors used reinforcement learning (an artificial intelligence technique) to ...
- 137k
4
votes
1
answer
547
views
Is it true that Public keys with even y coordinate correspond to private key that are less than n/2 and vice versa? (Secp256k1)
The question is somewhat complex and directed to clearing things out.
Suppose that $n$ is the order of the cyclic group. It $n - 1$ is the number of all private keys possible
...
- 43
1
vote
1
answer
294
views
Solving system of equation based on RSA
I have got 4 variables $n$, $x$, $y$, and $z$:
Here, $n = p\cdot q$ with $p$ and $q$ are distinct primes
\begin{align}
x &= m^p \bmod n\\
y &= m^q \bmod n\\
z &= m^n \bmod n\\
\end{align}
...
- 33
0
votes
1
answer
213
views
Problem in finding the inverse element in modular arithmetic
I'm new to modular arithmetic but it still is something that I think is pure mathematics that I don't get.
I have this problem 3 * d ≡ 1 mod 13. So I need to find ...
- 101
1
vote
1
answer
126
views
RSA: Does it worth to calculate missing CRT parameters when you have just N, E, D, P, Q?
OpenPGP defines RSA secret key in a way which differs from PKCS #1,having the aforementioned values plus U = P^-1 mod Q.
However, OpenSSL seems to work only with <...
2
votes
1
answer
484
views
Patterson's decoding algorithm for Goppa codes
From this Wiki page: given a Goppa code $\Gamma(g, L)$ and a binary word $v=(v_0,...,v_{n-1})$, its syndrome is defined as $$s(x)=\sum_{i=0}^{n-1}\frac{v_i}{x-L_i} \mod g(x).$$
To do error correction, ...
0
votes
0
answers
81
views
Can a modulo function be linearized or alternatively expressed?
In order to try to simplify or alternatively express cryptographic functions I wonder if the modulo function can be alternatively expressed. Could for example a Fourier series of a sawtooth wave or ...
- 123