Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

1
vote
2answers
47 views

Difference between when select x from $\mathbb{Z}_{p-1}$ and $\mathbb{Z}_p$ in discrete logarithm Problem?

Reading "Security Arguments for Digital Signatures and Blind Signatures" paper, I confused by some questions. Q1. when it refers to "El Gamal signature scheme", The key generation algorithm: it ...
7
votes
1answer
205 views

Is it hard to compute $g^{ab}$ when given $(g, g^a, g^b, \frac{a}{b})$?

We know that the CDH problem, computing $g^{ab}$ from given $(g, g^a, g^b)\in\mathbb Z_p^3$, is hard. Is it still hard with an auxilary information $\frac{a}{b}\bmod q$ (where both $p$ and $q$ are ...
0
votes
0answers
4 views

Why Chinese Remainder Theorem(CRT) will give unique $x \mod M$? [migrated]

If the $m_1, ..., m_r$are pairwise coprime, and if $a_1, ..., a_r$ are any integers, then system of $r$ conqruens $x \equiv a_ i \mod m_ i $ ($ 1\le i \le r$) has a unique solution modulo $M= m_1 * ...
0
votes
1answer
51 views

What is the significance of $\prod \limits_{i=1}^{t}m_i > p \prod \limits_{i=1}^{t-1}m_{n-i+1}$ in Asmuth–Bloom threshold SSS?

In this paper by Asmuth–Bloom on threshold SSS, the algorithm is as follows: Shares Distribution To distribute $n$ shares of a secret $K$ among the set of participants $P = \{ p_i : 1 ≤ i ≤ n\}$, ...
7
votes
1answer
588 views

Which properties of a group are used in the steps of Diffie Hellman?

I’m trying to understand which properties of a group are used in DHKE at each step. For example, Alice and Bob’s public keys appear to only use the closure property of a group and maybe identity (e....
6
votes
1answer
217 views

Why is a number of shares that is greater than a threshold required to construct secret?

In this paper of Asmuth–Bloom threshold SSS, the algorithm is as follows: Shares Distribution To distribute n shares of a secret $K$ among the set of participants $P = \{ p_i : 1 ≤ i ≤ n\}$, the ...
1
vote
0answers
40 views

Random Primes Conjecture [closed]

I know it is believed that primes appear to be randomly distributed among the integers. Is there a formal conjecture or theorem that expressly states that the occurrence of the prime numbers is ...
5
votes
0answers
56 views

Parity of the order of a element

Given an element $g$ in a cyclic group $G$ of known order $m$ its easy to test if $m$ has even or odd order. In other words $\textrm{ord}(g) \pmod 2$ can be computed easily. In some cases where the ...
2
votes
1answer
122 views

Solving discrete log in partially known group

Suppose I have a group $G$ of unknown order $n$ where $n=p^k\cdot s$, $\gcd(p,s)=1$, $p$ is a known prime, $k,s$ are unknown positive integers and $k,s\ge1$. (Known - $p$ and $p\mid n$, Unknown - $n,k,...
3
votes
1answer
137 views

Upper bounds on difference of RSA primes

I was wondering whether given a concrete $N = p \cdot q$ whether we can find a upper bound on $\Delta = | p - q|$ as function of $N$ e.g, $N^\delta$, and thus test whether a given $N$ is vulnerable ...
0
votes
0answers
51 views

What is the computational complexity of Coppersmith's bivariate algorithm?

Coppersmith's original paper Finding a Small Root of a Bivariate Integer Equation; Factoring with High Bits Known says the algorithm to find bivariate roots under certain conditions runs in ...
0
votes
2answers
317 views

How we can calculate AES Inverse SBox?

I am trying to find out the inverse of and SBox, but in vain, I have seen multiple questions over StackExchange, But I cant be able to solve my issue. As in this question, How are the AES inverse S-...
7
votes
1answer
255 views

Why is Approximate GCD a hard problem?

There are many Fully Homomorphic Encryption over the Integers schemes whose security is based on the intractability of the Approximate GCD (AGCD) problem. The paper Algorithms for the Approximate ...
1
vote
1answer
45 views

How can process algebra help to design security protocols?

Would you please tell me how process algebra could help me to design security protocols? More specifically, can I use it for proving the security of protocols? Is process algebra used for any ...
3
votes
0answers
60 views

Why do one-way accumulators use rigid integers as the modulus?

In the paper that introduced one-way accumulators, the author's justify their use of rigid integers as the modulus with the following: The advantage of using a rigid integer $n = pq$ is that the ...
10
votes
1answer
111 views

Sum of two squares problem

I would like to know if there is any existing research on the following problem: $$\text{For }a, b \in \mathbb Z \text{, given }n = a^2 + b^2, \text{output }a, b$$. Searching for "sum of squares", "...
2
votes
1answer
149 views

Understanding the Pohlig-Hellman algorithm

The paper has the following relation: $$y^{(p-1)/p_i} \equiv \alpha^{x(p-1)/p_i} \equiv \gamma_i^x \equiv \gamma_i^{b_0} \pmod p$$ where $\gamma_i = \alpha^{(p-1)/p_i}$. I understand this relation ...
1
vote
1answer
70 views

Is this problem same as discrete logarithm?

Given $g,h\in\mathbb Z_p$ where $g$ generates $\mathbb Z_p^\star$ Discrete logarithm problem is to find $z$ such that $g^z\equiv h\bmod p$ holds. Take the problem given $g,g',h$ where $g^z\equiv h\...
5
votes
2answers
880 views

Why do algebraic proofs apply to cryptography?

How do we know that the number theoretic and algebraic results used in cryptography provide a perfect model for the behavior of integers as implemented in computers? Does there exist a bijection ...
2
votes
0answers
74 views

Explanation of a proof of one of Shoup's lemmas

In Lower Bounds for Discrete Logarithms and Related Problems, Victor Shoup states the following lemma: Lemma 1 Let $p$ be prime and let $t \ge 1$. Let $F(X_1, \dots, X_k) \in \mathbb{Z} / p^t[X_1, \...
2
votes
1answer
59 views

Using Euler's theorem.. how can I get appropriate x..?

The question is this... $x^{29}\equiv4\pmod{91}$. Note that $91 = 7*13$. Compute an integer $x$. Since 91 is not prime number, I know I need to use Euler's theorem, not Fermat's. So I get $a^{...
4
votes
0answers
215 views

Is the matrix step of GNFS still the hardest part?

When the factorization of RSA-768 was announced in December 2009: the sieving took about 24 months and the matrix step took 119 days (4 months). So sieving took about 6 times as long. This is despite ...
-1
votes
1answer
81 views

I want to find the decryption keys of Alice and Bob for 3 pass protocol, how do I get C? or Ciphertext?

Okay so I wanted to know if my logic is correct for the approach of this practice problem that I'm doing in preparation for my final and see if I truly understand how the 3 pass protocol works so: <...
1
vote
0answers
62 views

Is it hard to determine whether a given matrix is the square of another matrix?

Given a matrix $A\in M_d(\mathbb Z_N)$, is it hard to determine whether there exists another matrix $B\in M_d(\mathbb Z_N)$ such that $A=B^2\bmod N$? Suppose the factorization of $N$ is unknown and ...
4
votes
2answers
178 views

Why does TWINKLE use light instead of current?

TWINKLE is a device devised by Adi Shamir to optimize the sieving step of GNFS. It consists of a cylinder, at the bottom of which are LEDs corresponding to factor base primes which blink with ...
1
vote
2answers
64 views

Is there any Information on the “Modular Approximate Greatest Divisor” problem?

The Approximate Greatest Common Divisor (AGCD) problem is the difficulty of obtaining the value $\ p\ $ when given samples of $\ pq_i + e_i$ for secret values $p, q_i, e_i$. I would like to know how ...
1
vote
0answers
119 views

discrete logarithm vs normal logarithm [duplicate]

Crypto schemes normally use discrete logarithm instead of normal logarithm. I think this has to do with the fact that discrete logarithm is hard to solve while normal logarithm isn't. Can someone ...
0
votes
1answer
1k views

Number encryption algorithm

I have a list of numbers. I will be calling a service(let's say accountant service) which is going to perform some operation on these list of numbers and will return me the final result number. I don'...
0
votes
1answer
462 views

How close to pure math is cryptographic theory? [duplicate]

I'm an undergraduate math student, and I'm thinking about topics for an undergraduate thesis. I have an interest in topological spaces and number theory, but I'm having trouble identifying a ...
2
votes
1answer
142 views

What is the correct elliptic curve representation?

I'm studing the basics of elliptic curve from various resource some more mathematical someone more practical. I know that the equation where the elliptic curves come from is the Weistraß equation $$...
3
votes
1answer
267 views

Diffie Hellman unsafe prime vulnerability

I have done some research about how the DH key exchange is unsafe if an unsafe prime p is used (that is, $p-1$ has a lot of small factors). Many answers here on StackExchange claim that for any factor ...
0
votes
1answer
72 views

Taking $p$ and $q$ to be the same value in paillier cryptosystem

I was implementing Paillier cryptosystem when I came across the fact that as soon as I take the primes $p$ = $q$, I start getting incorrect decryption results. As far as I can understand, when I take $...
3
votes
2answers
894 views

PhD in cryptography using elliptic curves [closed]

I am currently a MSc student in number theory and considering switching to a phD in cryptography. I would like to use number theory techniques. (i.e. RSA, elliptic curves, etc). The purpose of all ...
0
votes
1answer
128 views

Will reading “Elementary Number Theory” by David M. Burton be useful for Cryptography? [closed]

I am a Computer Science student and interested to learn Cryptography to be a researcher in this field. I heard that Number Theory is useful for Cryptography since there are some Crypto systems based ...
2
votes
2answers
187 views

More general - what is the hard problem of recovering r from r*p mod q?

I would like to know the cryptographic hard problem that is most closely tied to recovering integer $r$ from the modular product $r\times p\mod q$. (This is a simplification of an earlier post that ...
1
vote
1answer
64 views

What is the hard problem for this algebraic encryption construct?

I would like to know what cryptographic hard problem this reduces to. Select two large prime numbers $p$ and $q$, and let $N=pq$. Select a random positive integer $r$. Compute the encryption of ...
1
vote
0answers
67 views

Why use Phi(m) divide Order(p, m) to get slot number in HElib?

I am reading HElib source code, and have a confusion about FindM function: ...
1
vote
1answer
854 views

Difference between $Z^*_n$ and $Z_n$ [closed]

When studying cyclic groups I stumbled upon the following sentence: The ∗ in $Z_n^*$ stresses that we are only considering mulitplication and forgetting about addition on this site of stanford. I ...
-1
votes
1answer
187 views

Count elements with a given order in the multiplicative group $n=pq$ (RSA) [closed]

We know that the order of an element $a$ in the group $\mathbb Z_n^*$ is $k$ where $k|lcm(p-1,q-1)$ where p,q are distinct primes. Something else i think we know is that the elements that have order $...
4
votes
1answer
794 views

How to solve the Diffie-Hellman problem if $g$ is unknown?

I am trying to solve the Diffie-Hellman problem modulo a composite number $N$, which I have factored. In this question, it was answered how to deal with such a situation. But how can I solve the ...
4
votes
1answer
68 views

Result of expressions using modular arithmatic for group signatures

I read the following in a paper about group signatures called "A Practical and Provably Secure Coalition-Resistant Group Signature Scheme". In the sign part of paper the following expressions can be ...
0
votes
2answers
91 views

How can I make sure message m ∈ Zp

I am implementing ORUTA and using JPBC library for it. In one of the algorithms, for hashing a message, it is specified that for message m: $m \in \mathbb Z_p$ , for some large prime $p$. I have ...
2
votes
1answer
86 views

Strange modular expression in paper on group signatures

I've come accross the following expression in a paper: $$A_i=(C_2 * a_0)^{1/e_i} \bmod n$$ How to calculate $1/e_i$ in modular arithmetic? Or does it have some different meaning that I do not know? ...
0
votes
1answer
136 views

Order of an elliptic curve defined over a prime field

I found the following algorithm to find the generator of an elliptic curve: Find the order of the curve - N. Choose any random point on the curve - P. Find the order of that point - n. Calculate co-...
1
vote
1answer
304 views

Role of primitive roots in Pollard's P-1 factorization algorithm

I have recently been reading about different factorization algorithms and I came across this paper that discusses the Pollard's P-1 algorithm. In the footnote of the first page, it states... For ...
-1
votes
1answer
86 views

Proving additive inverse as generator of Z*p [closed]

Let there be $p\ ,q$ odd primes, such that $p=2q+1$. Let the be $a \in Z^*_p$ so that $a \not= \pm 1(mod\ p)$. Prove that if $a$ is not a generator of $Z^*_p$ then $-a$ is a generator of $Z^*_p$.
2
votes
1answer
133 views

Quadratic sieve for DLOG performance - theory vs actual?

Is there any report on comparing quadratic and number field sieve performance in theory vs actual data for discrete logarithm over primes? Is actual data better than theory in any way unexplained (I ...
1
vote
1answer
247 views

Generating Diffie-Hellman parameters

I'm trying to implement a diffie-hellman key exchange in c++, and I'm struggling with my missing understanding of math / group theory. Let's say I found a large prime number p - how can I find a ...
4
votes
1answer
107 views

Trying to implement the algorithm in Wikipedia regarding key exchange

I am trying to understand the reconciliation technique mentioned in Wikipedia page for Ring-LWE key exchange. Basically, if we intentionally choose x, y (or the coefficients of calculated shared key ...
0
votes
1answer
57 views

How to find g in Factoring-Based Trapdoor Hash Function

Please explain how to find a value of $g$ if $p,q$ are safe primes having $p'=(p-1)/2$ and $q'=(q-1)/2$ are also primes $n=p*q$ $\lambda(𝑛) = \operatorname{lcm}(𝑝 − 1, 𝑞 − 1) = 2𝑝'𝑞'$. How to ...