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
42 views

Finite Field Arithmetic _ Montgomery reduction

In an attempt to understand the mathematical operations related to encryption with elliptic curves, in particular finite field arithmetic (Modular reduction) I found in the Montgomery reduction that ...
Nawras Hussein's user avatar
1 vote
1 answer
121 views

How to calculate Legendre Symbol in secp256k1 Elliptic Curve

In this answer by fkraiem he proves a property that: $a^{(p-1)/2} = 1$ if and only if $x$ is even But this doesn't seem to work in my test with the secp256k1 Elliptic Curve. Here is my Python 2 ...
Devanshu Linux's user avatar
1 vote
0 answers
93 views

Number of elements in cyclic group that satisfy an exponent

I'm having trouble with solving the following question: Given two distinct prime numbers $p, q$ where $(p-1)$ and $(q-1)$ are not divisible by $3$, define $n=pq$. For how many elements in $\mathbb Z^*...
Eatay Mizrachi's user avatar
0 votes
1 answer
53 views

Solving modular polynomial equation modulo known factorization of a modulus is easy?

Let $f(x)\in\mathbb{Z}[x]$, let $N$ be an integer with known factorization into prime elements. I want to know why it is easy to solve efficiently the equation $f(x)=0\ mod\ N$.???
Mohammed Rahmani's user avatar
2 votes
0 answers
53 views

Can Index Calculus take advantage of small unknown?

The Index Calculus algorithm solves the Discrete Logarithm Problem of finding $x$ with $g^x\bmod p=b$ given $g$, $b$, and prime $p$. Assume $g$ is a generator, so that $x$ is uniquely defined in $[1,p)...
fgrieu's user avatar
  • 140k
2 votes
2 answers
330 views

Cost of solving multiple Discrete Logarithm Problems in the same group

We consider the Discrete Logarithm Problem of finding integer $x$ random in $[0,n)$ where $n$ is the group order, given $Y=G^x$ (or $Y=xG$) computed in the group noted multiplicatively (or additively),...
fgrieu's user avatar
  • 140k
0 votes
1 answer
93 views

Prove that if $e.d \equiv 1 \text{ mod } pq$ then it's impossible to have $e.d \equiv 1 \text{ mod } (p-1)(q-1)$

I am studying RSA cryptosystem and here is the question that came to my mind. Let's pick $p, q$ to be two primes and $n = p * q$. From that we calculate Euler's totient function: $$ \phi(n) = (p - 1)(...
QuestionEverything's user avatar
3 votes
0 answers
56 views

Are high-dimensional versions of NTRU cryptosystem more secure?

The basis for this question is a 1-dimensional NTRU cryptosystem. After some literature inspection I have found out it can be also generalised into higher algebras: quaternions (QTRU) and octonions (...
max's user avatar
  • 219
0 votes
0 answers
47 views

In RSA Encryption, Can I choose the public exponent e > m (modulus) ? or e > φ(n)? [duplicate]

In RSA ,the encryption, Can we choose the public exponent (e) greater than m (modulus) or e > φ(n) ? I wonder about choosing public key exponents (e) because the most information on the internet or ...
Nicha59's user avatar
  • 11
0 votes
0 answers
48 views

In RSA Encryption, Can the public exponent e > m (modulus) ? and can we choose any public key without paying attention to the conditions? [duplicate]

In RSA ,the encryption, Can we choose the public exponent (e) greater than m (modulus) or e > φ(n) ? I wonder about choosing public key exponents (e) because the most information on the internet or ...
Nicha59's user avatar
  • 11
0 votes
0 answers
34 views

Solving XOR modular system of equations

I have the following problem. Here's a rephrased version of your problem, keeping the LaTeX commands unchanged: We are given $n \in \mathbb{N}$, $p, q \in \mathbb{N}$, and $y \in \mathbb{N}^{n+2}$. ...
Kroki's user avatar
  • 111
1 vote
0 answers
43 views

Determining the Parity of Exponent b in Modular Exponentiation Given Three Known Values

I have three numbers x, a, and c, where both a and c are odd numbers. The number x is the output of the following function: $$ x = a^b\!\!\!\!\!\!\!\mod{c} $$ I am attempting to determine whether the ...
Puneet Jain's user avatar
0 votes
0 answers
207 views

Modular Binomial Problem

The solution to the problem of finding the primes $p$ and $q$ that have the following form: $$ c_1 = (a_1 p + b_1 q)^{e_1} \mod{N} \\ c_2 = (a_2 p + b_2 q)^{e_2} \mod{N} $$ Given the values of $c_i$, $...
redpanda2236's user avatar
2 votes
1 answer
91 views

Properties of Sums of Legendre Symbols

Context An unknown modulus N with 8 unknown prime factors $p_1, p_2, p_3, p_4, p_5, p_6, p_7, p_8$ a plaintext $m$ is encrypted with the formula $c = 2^m \mod N$ the only things the attacker know are ...
Cukurukuk's user avatar
2 votes
0 answers
44 views

Speedups for non-constant time modular arithmetic?

I am interested in modular arithmetic with respect to the prime $p = 2^{64}-2^{32}+1$. Thomas Pornin has some work on constant time implementation of arithmetic in $\mathsf{GF}(p)$ for this prime (the ...
Mark's user avatar
  • 12.4k
1 vote
1 answer
122 views

Solving equation of xor and mod operation

How do I solve equations like this $$(aX \oplus X+b) \bmod M = c$$ If a,b and c are known? and if i have system of of equation with different b values, is it solvable? I am particularly interested in ...
Sora's user avatar
  • 11
1 vote
1 answer
97 views

Finding two inputs [i, j] of a custom Hash function where their Hashes are [H(i), H(j)] = [H(i), H(i)^2] [closed]

I came upon the following hash function (pseudo-code): ...
bd55's user avatar
  • 33
1 vote
1 answer
161 views

What is the inverse of this generalised automaton (based on bitwise XOR and modular addition)?

Section 4.1 of the paper “Nonlinear Diffusion Layers” [Y. Liu, V. Rijmen, G. Leander] defines the nonlinear function $\rho$ over $\mathbb{F}_{2^m}$ as follows: $$\rho : \mathbb{F}_{2^m}^4 \to \mathbb{...
lyrically wicked's user avatar
-2 votes
2 answers
472 views

How to map elements from subgroup to larger subgroup of its parent group?

The following context is based on elliptic curves in short-weierstrass form y^2 = x^3 + b. pls read carefully- I am looking for a function/formula/algorithm that can be applied on any curve, say for e....
Homer's user avatar
  • 7
0 votes
1 answer
73 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
112 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 ...
Princess Mia's user avatar
2 votes
1 answer
130 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
66 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 ...
Princess Mia's user avatar
1 vote
2 answers
94 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
  • 95
0 votes
0 answers
45 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
353 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
1 vote
2 answers
80 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,125
1 vote
1 answer
318 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
1 answer
147 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
612 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
31 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
634 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
96 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
148 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
147 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
200 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
161 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
125 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
3 votes
1 answer
43 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
  • 558
3 votes
1 answer
607 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
  • 335
2 votes
1 answer
175 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
34 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
101 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
216 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
  • 33
3 votes
1 answer
415 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
104 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 ...
unsigned_int2's user avatar
1 vote
1 answer
95 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
2k 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
388 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,575
1 vote
1 answer
282 views

Is the generator point in the curve in secp256k1?

Here is the fixed script ...
Reda Bourial's user avatar

1
2 3 4 5
10