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
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 ...
Aman Sharma's user avatar
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$,...
axk's user avatar
  • 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 ...
Shmuel's user avatar
  • 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 ...
Justice Almanzar's user avatar
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 ...
Shmuel's user avatar
  • 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 $$ ...
Zpeed78's user avatar
  • 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) \...
bjpo027's user avatar
  • 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 ...
user432944's user avatar
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(...
Sam Jaques's user avatar
  • 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 ...
JMC's user avatar
  • 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),...
Maltoon Yezi's user avatar
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 ...
Hendi's user avatar
  • 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 ...
TheBestMagician's user avatar
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 ...
Kevin Stefanov's user avatar
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 ...
fandreas's user avatar
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?
Ayush's user avatar
  • 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 ...
Jason L. B.'s user avatar
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 ...
joemelsha's user avatar
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$, ...
smitc29's user avatar
  • 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. ...
jdbertron's user avatar
  • 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) ...
crypto12's user avatar
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. ...
pintor's user avatar
  • 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 ...
Rory's user avatar
  • 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 ...
Paul Miller's user avatar
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. ...
meran_kud's user avatar
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 ...
Ricky's user avatar
  • 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 ...
bd55's user avatar
  • 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$...
zerver's user avatar
  • 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 ...
empty_stack's user avatar
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 ...
Brendan's user avatar
  • 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 ...
ubiquibacon's user avatar
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 ...
Ievgeni's user avatar
  • 2,554
1 vote
1 answer
158 views

Is the generator point in the curve in secp256k1?

Here is the fixed script ...
Reda Bourial's user avatar
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 ...
empty_stack's user avatar
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 ...
NewbieBoy's user avatar
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, ...
SarkoxedaF's user avatar
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 ...
mmazz's user avatar
  • 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 ...
Roman's user avatar
  • 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 ...
Neel Basu's user avatar
  • 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 ...
Gerrie's user avatar
  • 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 ...
falc's user avatar
  • 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 ...
Creeptographer's user avatar
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 ...
tur11ng's user avatar
  • 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 ...
fgrieu's user avatar
  • 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 ...
Emma Lincoln's user avatar
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} ...
CipherNewbie's user avatar
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 ...
Panagiss's user avatar
  • 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 <...
Nickolay Olshevsky's user avatar
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, ...
Creeptographer's user avatar
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 ...
David Jonsson's user avatar

1
2 3 4 5
10