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
2 votes
1 answer
668 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 ...
-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....
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 ...
1 vote
1 answer
122 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 ...
1 vote
0 answers
94 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^*...
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$.???
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)...
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),...
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),...
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)(...
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 (...
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 ...
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 ...
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 ...
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 ...
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}$. ...
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 ...
4 votes
1 answer
797 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 ...
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(...
0 votes
0 answers
216 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$, $...
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 ...
1 vote
1 answer
123 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 ...
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): ...
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{...
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$,...
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 ...
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 $$ ...
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 ...
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 ...
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) \...
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 ...
4 votes
2 answers
508 views

Speed up modular exponentation with fixed base and modulus

Can someone explain, how $a^x \mod N$ can be speeded up, when $a$ and $N$ are known constants? How big is the gain and what resources are needed? https://www.imperialviolet.org/2013/05/10/...
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 ...
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 ...
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 ...
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 ...
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 ...
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?
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. ...
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$, ...
2 votes
1 answer
3k views

Deriving a decryption equation

Consider a very simple symmetric block encryption algorithm, in which 32-bits blocks of plaintext are encrypted using a 64-bit key. Encryption is defined as $C = (P\oplus K_L) \boxplus K_R$ where $...
1 vote
1 answer
114 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 ...
3 votes
2 answers
3k 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 ...
3 votes
3 answers
4k views

Point decompression on an elliptic curve

I'm programming an elliptic curve cryptosystem and I'm having difficulty with decompressing points. The following information is from my project specification as to my understanding: Given a point $x$...
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. ...
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 ...
2 votes
1 answer
176 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 ...
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. ...
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 ...
1 vote
1 answer
217 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 ...

1
2 3 4 5
10