Questions tagged [number-theory]

Number theory is the study of the properties and construction of numbers, particularly integers. Prime numbers are of particular interest to number theorists and consequently cryptographers as they are considered the "building blocks" of numbers and produce many interesting results which are useful in cryptography. Questions covering number theory and primes should use this tag; questions involving finite fields and groups might use this tag if relevant.

Filter by
Sorted by
Tagged with
1 vote
0 answers
30 views

Should not we eliminate $\pm 1$ from $\mathbb{Z}^\times_N$ in RSA accumulators?

RSA accumulator is an authenticated set built from cryptographic assumptions in hidden-order groups such as $\mathbb{Z}^\times_N$. Any set $S=\{e_1,e_2,\ldots,e_n\}$ can be commited via a commitment $...
Somudro Gupto's user avatar
1 vote
0 answers
35 views

How to know the number of digits in the decimals place in elliptic curve division result?

$p$ - is the order of the finite field $n$ - is the order of the group. Private keys can range from $1$ (the generator point $G$) to $n - 1$. All the private keys ($Priv$) lie in certain ranges of 2. $...
Maltoon Yezi's user avatar
1 vote
1 answer
69 views

How zetas are computed in CRYSTALS-Kyber?

As shown below it explains how generate zetas table and use it. But curious thing is that how KYBER_ROOT_OF_UNITY constant is generated ? I've tried multiple ways to generated it and cannot explain ...
Ali ÜSTÜN's user avatar
1 vote
3 answers
657 views

(Complexity Theory) Given a large non-semiprime, is there a hard to compute but easy to verify problem?

Let's say I had an arbitrary number that was large, say 512 bits or bigger, but wasn't necessarily a semiprime. What is a computation that I could do on this number that would give me a unique ...
Starscream512's user avatar
1 vote
0 answers
88 views

Understanding Gentry's initial FHE construction based on ideal lattices

I am trying to understand the encryption procedure in Craig Gentry's initial construction for FHE described in Fully Homomorphic Encryption Using Ideal Lattices. Unfortunately after repeated attempts ...
Parham's user avatar
  • 111
2 votes
1 answer
69 views

n-bit addition over $GF(2^n)$ vs. addition modulo $2^n$

I am currently studying the cryptanalysis of Speck, but I am feeling confused about the addition in Speck. I am not sure whether the addition in Speck is done through n-bit addition over $GF(2^n)$ or ...
35 honglang's user avatar
1 vote
1 answer
68 views

Division in Finite Rings of Order 2^ℓ

During one of the seminars at my university on Cryptography, the presenter said that while computing $x/y$ over Finite Rings $\mathbb Z_{2^\ell}$, there exist some problems such as: $y^{-1}$ may not ...
Sumana Bagchi's user avatar
2 votes
1 answer
54 views

Reflecting a point on the Edwards curve

Let's say we have a point $nP = (x,y)$ on a curve $E$ over a prime $p$. The corresponding Edwards curve coordinates are $(u,v)$. I want to construct the point corresponding to $(u,-v)$ on the Edwards ...
mtheorylord's user avatar
1 vote
2 answers
69 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
1 answer
105 views

finding r-th root in $\mathbb{Z}/n\mathbb{Z}$

I was reading the paper One-way Accumulators: A Decentralized Alternative to Digital Signatures by Benaloh and de Mare [link], and in section 4.2, they say that given $z\in (\mathbb{Z}/n\mathbb{Z})^*$ ...
vxek's user avatar
  • 467
2 votes
1 answer
903 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
1 answer
161 views

Special algorithms for edge cases of binary arithmetic?

I have several mathematical operations on binary numbers that are special cases of more general arithmetic operations. I am wondering whether there exist more specialized algorithms purpose-made for ...
Kevin Stefanov's user avatar
3 votes
1 answer
188 views

Purpose of the b1, b2, b3.... terms in Rabin-Miller Primality Test

In Rabin-Miller primality test, let N be the number you're checking for primality. Here N = 78007. Let m be the number you get after dividing (N - 1) by 2 several times until you can no longer do so. ...
Kevin Stefanov's user avatar
1 vote
1 answer
503 views

Challenges like RSA factoring challenge

RSA factoring challenge is a famous one and is still not completely solved. Are there similar challenges for Discrete log over $\mathbb Z_p^*$? Discrete log over Elliptic curves? LWE? LPN?
Turbo's user avatar
  • 908
1 vote
1 answer
607 views

Rabin-Miller Primality Test - Elaboration needed

In short, my question is: What exactly do people mean when they say that "The more you apply the Rabin-Miller test to a number, the more certain you can be that the number you're testing is prime....
Kevin Stefanov's user avatar
5 votes
1 answer
478 views

Discrete Logarithm Challenges and Records

I am wondering whether there are any current challenge problems for Discrete Logarithms. Specifically in $\mathbb{Z}_p^\ast$ as well as in elliptic curve groups. It turns out CERTICOM still has some ...
kodlu's user avatar
  • 22.5k
2 votes
1 answer
189 views

Why is $d = e^{-1} \mod \phi(N) \equiv e^{\phi(N)-1} \mod \phi(N)$ and not commonly used in RSA key generation?

On some lecture slides regarding to RSA-Encryption, the formula for calculation of the private key is given as $d = e^{-1} \equiv e^{\phi(N)-1} \mod \phi(N)$. The second equation is justified by the ...
Mr. McNiki's user avatar
1 vote
1 answer
94 views

Non probabilistic algorithm : Given secret key $d$ we can factorize $n$ assuming $e$ is small

I read in an introduction to a paper that if $e$ is small enough and we were given secret key $d$ in RSA, then there is an efficient deterministic algorithm to factorize $n$. I've searched about that ...
tonythestark's user avatar
2 votes
2 answers
129 views

Verification through prime modulus

Asking this question here since it has a flavor similar to some cryptographic protocols. How likely are two integers which are smaller than some threshold, mod by some prime number to have the same ...
Sam's user avatar
  • 123
1 vote
1 answer
267 views

Proving the generator criterion for group $Zp$

I am trying to understand how to find a generator of Zp. How to find generator $g$ in a cyclic group?. I have heard that we can pick random a Zp and for each primitive d| p-1 check wether: a^[(p-1)/...
tonythestark's user avatar
1 vote
0 answers
25 views

Possible plain text needed on a congruence modulo - based encryption

Suppose m is a positive integer converted from the plain text in bytes. And there are two positive integers a, ...
Robert Huang's user avatar
0 votes
2 answers
129 views

Computing the eth root in Z(N)* i.e set of all elements coprime to N

I understand that it is easy to compute eth root in Z(P)* but what about with Z(N)? I know that it requires the factorization of N but what does that actually mean? What is an example of calculating ...
testCrypto's user avatar
1 vote
1 answer
174 views

Does it weaken a RSA modulus to publish a generator of a small subgroup?

Let $n = P\cdot Q$ be the product of two safe primes $P = 2p+1$ and $Q=2q+1$. Let $g$ be a generator of $C_{p} \subset \mathbb{Z}_n^*$, the multiplicative subgroup of order $p$. In other words, $g^p = ...
RobinLinus's user avatar
2 votes
2 answers
195 views

Proving in zero-knowledge the "sign" of a discrete logarithm in groups of unknown order

Suppose we have the description of a group $\mathbb{G}$, a group of unknown order: the size of the group is unknown. For instance, an RSA group ($\mathbb{Z}^{*}_N,$ where $N=pq$ for unknown primes $p$ ...
István András Seres's user avatar
3 votes
1 answer
97 views

Do ideal non-cyclotomic lattices provide better compression in lattice-based cryptography?

Let $f \in \mathbb{Z}[x]$ be an irreducible polynomial of degree $N$ and $q \in \mathbb{N}$. Consider the rings $R := \mathbb{Z}[x]/f$ and $R_q := R/q$. Obviously, an element of $R_q$ can be ...
Dimitri Koshelev's user avatar
1 vote
1 answer
96 views

Expectation of the size of algebraic norm in power of two cyclotomic field

Let $\mathcal R$ be the ring of integers of a power of two cyclotomic field. That is, $\mathcal R = \mathbb Z[x] /\langle x^{2^k}+1\rangle $ for some integer $k$. We denote $\mathcal R / q \mathcal R$ ...
Ring-LWE's user avatar
1 vote
1 answer
546 views

Specific RSA challenge

It was a challenge from CTF (ended), but I didn't solve it. p, q = keygen(512) n = p * q flag = bytes_to_long(flag) enc = pow(n + 1, flag, n**3) So we have module ...
darkside's user avatar
2 votes
1 answer
152 views

Significance of having remainder $3$ when divided by $4$ for both $p$ and $q$ in BBS

In the Blum Blum Shub random number generator, we take two random prime numbers $p$ and $q$ such that both have a remainder of $3$ when divided by $4$. My question is why can't we just take any $2$ ...
swarna islam's user avatar
0 votes
1 answer
48 views

Precise heuristic for size of a uniform sample in $(\mathbb{Z} / N \mathbb{Z})^\times$

I'm primarily a mathematicians dipping my toes into cryptography, and I have often seen/heard cryptographers use the heuristic that a uniformly random sample $a$ from $(\mathbb{Z} / N \mathbb{Z})^\...
stillconfused's user avatar
0 votes
0 answers
291 views

RSA with huge ciphertext

I am trying to find the flag from an RSA ciphertext, I am able to get the factors from factordb.com but the given e is not ...
CipherNewbie's user avatar
1 vote
1 answer
75 views

Does a list of discrete log equations reveal information?

Given public generator $g$ of some cyclic group, a secrets $x\in Z_q$, and public pairs $(a_1,b_1),...,(a_n,b_n)$ (where $a_1,...,a_n$ are selected at random from a big set), and prime p, that ...
Doron's user avatar
  • 99
2 votes
1 answer
131 views

Can functional encryption encrypt and decrypt negative integers?

I want to use DCR-based functional encryption for encryption and decryption purpose. However, I'm unsure whether DCR-based functional encryption can support negative integers. Is there any ...
Angelina's user avatar
1 vote
1 answer
343 views

If RSA uses $e$ with $\gcd(e,\phi(N))\ne1$ but $e$ is hard to factorize has an adversary still an advantage in finding $d$ for $m^{ed}\equiv m\mod N$?

Usually RSA uses an encryption exponent $e$ with $\gcd(e,\phi(N))=1$. This question shows why that need to be the case: For $\ne1$ there might exist no decryption exponent $d$ because other $m'\ne m$ ...
J. Doe's user avatar
  • 433
1 vote
1 answer
58 views

Secure modification of DSA?

In DSA, we compute the signature $(r,s)$ on $m$ by sampling $k\in\{1,...,q-1\}$ and then computing $r := g^k \bmod p$ $s := k^{-1}*(m+x*r) \bmod q$ During verification, we compute $v:=g^{m*s^{-1}}*y^{...
mti's user avatar
  • 655
0 votes
1 answer
225 views

What does Euler's theorem have to do with RSA?

In RSA we compute e (encryption key) and d (decryption key) $\bmod phi(n)$ and not $\bmod n$, so how come when we get the keys and encrypt and decrypt we use $\bmod n$ not $\bmod phi(n)$ using the ...
ezio's user avatar
  • 157
0 votes
1 answer
252 views

Additively homomorphic (modified) RSA?

Is there a way to modify the RSA so that it's homomorphically additive? I did some research and came across a paper which describes MREA (Modified RSA Encryption Algorithm), an RSA modification that, ...
Arya513's user avatar
5 votes
1 answer
319 views

Which is the smallest, cyclic in 3 directions, consistent structure of random values which can be hidden at the adversaries machine? (some comparison)

Or more general each member can be part of up to three 2D locally euclidean planes of 2 different dimensions each. (each of those planes is cyclic in two orthogonal directions, like a torus) Given ...
J. Doe's user avatar
  • 433
2 votes
1 answer
49 views

Duality Results for Some Module Lattices

Let $R$ be the ring of integers of a cyclotomic field $\mathbb{Q}(\zeta_n)$, where $n$ is a power of two, and $\boldsymbol{a} \in R_{q}^{m}$, for $m\in\mathbb{Z}^+$, $q\in\mathbb{Z}_{\geq2}$ prime. ...
a196884's user avatar
  • 381
6 votes
2 answers
1k views

RSA with exponent being a factor of modulus

This weekend I participated in a CTF, but came across a task that I wasn't able to solve. I can't find any write-ups so I hope you can help me. Given: $$ n = pq\\ c_1\cong m_1^{\hspace{.3em}p} \mod n\\...
limeeattack's user avatar
1 vote
1 answer
57 views

Division by $2$ or principal root with DH oracle

Assume $g$ is generator of multiplicative group modulo prime $p=2q+1$ where $q$ is prime. Assume we know $g^{2t}\bmod p$ and $g^{2}\bmod p$ and assume we can have access to a Diffie-Hellman oracle. ...
Turbo's user avatar
  • 908
2 votes
1 answer
196 views

Distribution of group elements with chosen bits and hardness of discrete log problem

For generator $g$ of order $n$ the group elements $y=g^x$mod $n$ are uniformly distributed because of the modulo operation. Suppose however that from the original output space $Y$, we only consider ...
Panos's user avatar
  • 324
3 votes
2 answers
221 views

Common exponent problem related to discrete logarithms assuming Diffie Hellman oracle

Let $g$ be a generator of multiplicative group mod $p$ a prime. Suppose we know $$g^{a+km_1}\bmod p$$ $$g^{b-km_2}\bmod p$$ $$g^{a+k'm_3}\bmod p$$ $$g^{b-k'm_4}\bmod p$$ where $m_2m_3-m_4m_1=\phi(p)$ ...
Turbo's user avatar
  • 908
1 vote
0 answers
125 views

Working the multivariate Coppersmith algorithm

I recently studied the multivariate Coppersmith algorithm. Let $f(x)$ be $n$-variate polynomial over $\mathbb{Z}_p$ for some prime $p$. Informally, the multivariate Coppersmith's theorem stated that ...
filter hash's user avatar
1 vote
1 answer
167 views

On access to a Diffie Hellman oracle

Assume $g$ is generator of multiplicative group modulo prime $p$. Assume we know $g^X\bmod p$ and $g^{XY}\bmod p$ and assume we can have access to a Diffie-Hellman oracle. Can we find $g^Y\bmod p$ in ...
Turbo's user avatar
  • 908
1 vote
1 answer
38 views

Internal direct product of group of invertible elements in a Paillier modulus

Let $p$ and $q$ are Sophie-Germain primes such that $p=2p'+1$ and $q=2q'+1$. Also let $n=pq$ and $n'=p'q'$. In Section 8.2.1 of this paper, the internal direct product of $\mathbb{Z}_{n^2}^*$ is shown ...
kentakenta's user avatar
0 votes
1 answer
139 views

Breaking RSA with knowledge of the secret key $(n, d)$

I am following the discussion in Koblitz in the second paragraph in the RSA section (page 94 on my edition).The goal is to show that knowledge of an integer $d$ such that $$m^{ed}\equiv m \mod n$$ for ...
Creeptographer's user avatar
3 votes
0 answers
294 views

Elliptic Curve how to calculate y value [duplicate]

I have been reading the book Mastering Bitcoin written by Andreas. It was the process of compressing public keys that hurt my mind. Specifically, a public key after being generated from a private key ...
John Pham's user avatar
1 vote
2 answers
207 views

How to find the extractor in the Knowledge-of-Exponent Assumption?

From Mihir Bellare's paper Let $q$ be a prime such that $2q +1$ is also prime, and let $g$ be a generator of the order $q$ subgroup of ${Z^∗}_{2q+1}$. Suppose we are given input $q$, $g$, $g^a$ and ...
user93353's user avatar
  • 2,211
0 votes
1 answer
86 views

An equivalent definition for shamir secret sharing?

Taking into account this paper I will write here a definition that the authors provide. $\textbf{Definition:}$ (linear secret sharing scheme). A $(t,n)$ secret sharing scheme is a linear secret ...
Hunger Learn's user avatar
-1 votes
1 answer
49 views

How to define a cryptosystem when the encryption-decyrption scheme is based on Shamir's secret sharing scheme?

I would like to make a parallelism between Shamir's secret sharing scheme and how to define a cryptosystem where the encryption scheme is based on secret sharing. To begin with I do not know if there ...
Hunger Learn's user avatar

1
2 3 4 5 6