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
1 answer
47 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 ...
user avatar
  • 21
2 votes
1 answer
64 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 ...
user avatar
1 vote
1 answer
94 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$ ...
user avatar
  • 475
1 vote
1 answer
46 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^{...
user avatar
  • 439
0 votes
1 answer
100 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 ...
user avatar
  • 47
0 votes
1 answer
68 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, ...
user avatar
5 votes
1 answer
252 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 ...
user avatar
  • 475
0 votes
0 answers
16 views

Using Coppersmith for a second trivariate polynomial

I have a trivariate polynomial whose roots I am interested. The polynomial has monomials in $\{X^4,X^2,X^2Y,X^2Z,1\}$. What is the best way to generate the lattice and apply $LLL$ so that I can get a ...
user avatar
  • 882
2 votes
1 answer
33 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. ...
user avatar
  • 349
6 votes
2 answers
540 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\\...
user avatar
1 vote
1 answer
47 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. ...
user avatar
  • 882
2 votes
1 answer
179 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 ...
user avatar
  • 164
3 votes
2 answers
167 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)$ ...
user avatar
  • 882
1 vote
0 answers
55 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 ...
user avatar
1 vote
1 answer
81 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 ...
user avatar
  • 882
1 vote
1 answer
28 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 ...
user avatar
0 votes
1 answer
72 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 ...
user avatar
3 votes
0 answers
284 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 ...
user avatar
1 vote
2 answers
97 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 ...
user avatar
  • 1,637
0 votes
1 answer
68 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 ...
user avatar
-1 votes
1 answer
48 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 ...
user avatar
2 votes
0 answers
30 views

Centrality of Gaussian distribution for LWE error

Consider the LWE problem. Let $A$ be an $m \times n$ matrix, $x$ is an $n \times 1$ vector, $u$ is a $m \times 1$ vector, and $e$ is sampled from a Gaussian distribution. We are given either $Ax + e ~~...
user avatar
0 votes
0 answers
35 views

How can I enrich this mechanism of communication to become more efficient and secure?

Suppose that we have a Bayesian game, where $t_i\in T_i$ denotes the type of player $i$. Say that we have a communication game (communication equilibrium). The players do send each other an encrypted ...
user avatar
1 vote
0 answers
64 views

Building an Adversary for a PRF game

Here is the game: How can I make an $\mathcal{O}(k^2)$-time adversary making only one query to its Fn oracle and achieving advantage $= 1 - 1/(p-1)$ Here is my idea so far: query $2^{-1}$, which when ...
user avatar
2 votes
1 answer
119 views

Sage code for finding generator matrix of MDS code

Let $L$ be an $[n,k]$ code. A $k\times n$ matrix $G$ whose rows form a basis for $L$ is called a generator matrix for $L$. A linear $[n,k,d]$ code with largest possible minimum distance is called ...
user avatar
  • 23
1 vote
1 answer
89 views

What are the expected values of a particular rotational-XOR property of a sequence of random bitstrings?

Assuming that $x$ is a sequence of $l$ bits and $0 \le n < l$, let $R(x, n)$ denote the result of the left bitwise rotation of $x$ by $n$ bits. For example, if $x = 0100110001110000$, then $$\begin{...
user avatar
0 votes
0 answers
55 views

Matrix formulation of Number-theoretic transforms (NTT)

I have two polynomials over a finite field. I am trying to compute the product of these polynomials using Number-theoretic transforms. For my use case, it makes sense to do this in the matrix form. ...
user avatar
1 vote
0 answers
88 views

Modifying discrete logarithm problem in Zp by selecting a subset of group elements

Let $g$ generator of cyclic group $Z_p$ of order $p-1$, where $g$ can generate all group elements $\alpha \in Z_p$ as $\alpha = g^x$mod$p$, $x \in (0..p-1)$, where the discrete logarithm problem is ...
user avatar
  • 164
0 votes
1 answer
87 views

RSA: why $( e^{-1} ~\text{mod}~ n \cdot \varphi(n)) ~\text{mod}~ \varphi(n) = e^{-1} ~\text{mod}~ \varphi(n)$ holds for a specific setting of RSA

Let $p,q$ are primes and $n = pq$ as in every RSA setting and now use a random $e$ that holds the following properties $gcd(e, \phi(n)) \neq 1$ $(e^{-1} ~\text{mod} ~\phi(n))^{4}\cdot3 < n$ $e^{-1}...
user avatar
0 votes
1 answer
110 views

zkSnark Intro by Maksym Petkus: Is the polynomial defined over $Z$ or is it defined over $Z_n$?

I am reading this explanation of zkSnark written by Maksym Petkus - http://www.petkus.info/papers/WhyAndHowZkSnarkWorks.pdf Here he has a polynomial $p(x) = x^3 − 3x^2 + 2x$ and the homomorphic ...
user avatar
  • 1,637
2 votes
1 answer
165 views

zkSnark: Restricting a Polynomial

I am reading this explanation of zkSnark written by Maksym Petkus - http://www.petkus.info/papers/WhyAndHowZkSnarkWorks.pdf I have understood everything in the first 15 pages. In 3.4 Restricting a ...
user avatar
  • 1,637
0 votes
1 answer
126 views

Setting up the discrete logarithm framework

The discrete logarithm problem over prime cyclic groups consist of finding $x$ satisfying $g^x\equiv h\bmod p$ where $g$ is generator of multiplicative group $\mathbb Z/p\mathbb Z$ at a large prime $p$...
user avatar
  • 882
1 vote
1 answer
78 views

Extracting genome from a Ciphertext [closed]

Is it Probable to extract the ciphertext's genome and Visualizing it ? Converting this: ...
user avatar
  • 1,854
-1 votes
1 answer
62 views

Is there some function of $n$ that is a multiple of $\phi(n^2)$?

Not sure which forum to post this question so here is a link to it from MSE. This is to adapt the approach of Fermat's Little Theorem to the Paillier encryption system. I understand that this will ...
user avatar
1 vote
1 answer
137 views

Pollard's p - 1 - how do you set the bound & how do you set the base numbers

In Pollard's p-1 algorithm for factoring N, you try to find a L such that p - 1 divides L. Then you check $gcd(pow(a,L,N)- 1, N)$. If 1 < gcd < N, then you have found one of the factors. I have ...
user avatar
  • 1,637
0 votes
1 answer
91 views

Simple question about BGV scheme

While I'm trying to implement BGV scheme myself, I found that I'm really confusing about the encryption and decryption of the scheme. Here's my understanding: Let $p$ be a plaintext modulus and $q$ be ...
user avatar
1 vote
1 answer
142 views

Why is factorial used in Pollard's $p - 1$ algorithm?

Why exactly do we use factorial for finding an $L$ which is divisible by $p - 1$? Pollard's algorithm is about B-powersmooth numbers & not B-smooth numbers. So where exactly does the factorial ...
user avatar
  • 1,637
4 votes
2 answers
361 views

Is FFT for power-of-two cyclotomic rings possible if q is not 1 modulo 2n?

For RLWE (Ring Learning With Errors) scheme, we use $R_{q} = \mathbb{Z}_{q}[x]/(x^{n} +1) = \mathbb{Z}_{q}[x]/(\Phi_{2n}(x))$ where $n = 2^{d}$ for some $d$. Since there exists $2n$-th root of unity ...
user avatar
0 votes
0 answers
35 views

What is the number of fixed plaintexts of RSA [duplicate]

Considering RSA, $n=p\,q$ with $p,q$ odd primes and the public key $(n,e)$, where $\gcd(e,\phi(n))=1$, I need a hint on how to show that the number of plaintexts with $E_e(x)=x$ equals $\gcd(e-1,p-...
user avatar
1 vote
1 answer
128 views

Use the Index Calculus to solve for $19^x \equiv 205\pmod{337}$, using the factor base $B=\{2,3,5,7\}$

I'm supposed to use the following information to solve the question, but I don't know how. $$\begin{align} 19^2 &\equiv 2^3 \times 3^1 \times 5^0 \times 7^0&\pmod{337}\\ 19^5 &\equiv 2^5 \...
user avatar
  • 11
1 vote
1 answer
98 views

Diffie Helman obtaining $g^y \bmod p$ from $g^{xy} \bmod p$ and $g^x \bmod p$

This may seem like a strange question. Lets say I have $g^x \bmod p$ and $g^{xy} \bmod p$. How can I efficiently obtain $g^y \bmod p$? I assume I must use modular inverse but I don't know where.
user avatar
1 vote
0 answers
118 views

RSA with Carmichael number

I've to prove that RSA still works with a public key $(e,pq)$ where p is a prime and q is a Carmichael number such that $q<p$ and $\gcd(e,(p-1)(q-1))=1$ I know how RSA works wiht $p,q$ primes but ...
user avatar
2 votes
0 answers
64 views

Advice for career change to crypto? [closed]

I'll keep this brief. I'm a maths teacher in the UK looking at a career change into cryptography, especially the mathematical side of it - I've studied analytic number theory recently and really ...
user avatar
  • 21
9 votes
0 answers
209 views

How many additions modulo $2^k$ and multiplications in $\mathbb F_{2^k}$ are needed to resist cryptanalysis?

Consider a $k$-bit block cipher with $r$ rounds, and key composed of $r$ subkeys $K_i\in\{0,1\}^k-\{0^k\}$ (that is, non-zero $k$-bit bitstrings), for $i\in[0,r)$. Plaintext is $P=S_0\in\{0,1\}^k$, ...
user avatar
  • 124k
1 vote
0 answers
155 views

Where is factoring if discrete logarithm is broken?

Assume given $g^X\equiv h\bmod p$ where $g$ is of order $\frac{\lambda(p)}2$ where $\lambda(p)$ is Carmichael Lambda function applied to prime $p$ (so $2$ is invertible in exponent) we can compute $X$ ...
user avatar
  • 882
-1 votes
1 answer
55 views

proving an abelian group

I am reading this to understand more on abelian group. I could not understand some steps. https://yutsumura.com/prove-a-group-is-abelian-if-ab3a3b3-and-no-elements-of-order-3/ "Taking the square ...
user avatar
0 votes
0 answers
46 views

Composing subexponential L-function

Suppose $y=f(x)$ and $z=g(y)$ such that $y\in L_x[a,b]$ and $z\in L_y[c,d]$, where $L$ is the usual sub-exponential asymptotic notation $$L_x[a,b] = \exp\left((b+o(1))(\log x)^a(\log\log x)^{1-a}\...
user avatar
0 votes
1 answer
68 views

How to caculate the summation of successive modular inverses?

$p$ is a big prime. $p>2^{2048}$. So how to caculate the summation of successive modular inverses over $p$? $$ \sum_{i=1}^{\frac{p+1}{2}-1}{i^{-1}}\pmod p $$ As to $p$ is a big prime, it's ...
user avatar
  • 13
0 votes
1 answer
136 views

Lifting a congruence $f(X) \equiv gh (\textrm{mod} \ p)$ to a higher power moduli

I have the polynomial ring $R = \mathbb{Z}[X]/(X^N - 1)$ with $N = 11$ and $h \in R$ with \begin{equation*} h = 7 -11X - 7X^2 -12X^3 + 8X^4 - 11X^5 + -8X^6 + 11X^7 - 4X^8 + 2X^9 + 3X^{10} \end{...
user avatar
0 votes
1 answer
32 views

Finding product of two unknown numbers each raised to a known power

Let $G$ be a group, and let $a, b\in G$, and let $[3] = \{0,1,2\}$. Let $(x_i,y_i)$ for $i\in[3]$ be known constants. Assume that I know the elements: $$c_i = a^{x_i}b^{y_i},\quad i\in[3]$$ Then, ...
user avatar

1
2 3 4 5