Stack Exchange Network

Stack Exchange network consists of 174 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.

7
votes
1answer
561 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
212 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
55 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
103 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
131 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
47 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
189 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
225 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
43 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
57 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 ...
9
votes
1answer
109 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
120 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
62 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
71 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
58 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
212 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
59 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
61 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 ...
0
votes
0answers
46 views

Proof that previous numbers in a series must have existed before next number

A system provides users with a number when they query it for one. The system may provide numbers that increment by 1, 2, x or an entirely different pattern. For example, the system may start at 0 ...
4
votes
2answers
174 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 ...
0
votes
0answers
170 views

Question about RSA least significant bit oracle attack

According to this question, you can attack RSA by knowing the parity of arbitrary plaintexts. However, the question has a puzzling statement: If an attacker intercepts an encrypted plaintext $C = ...
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 ...
0
votes
0answers
21 views

Alternative Hard Problem to Prime Factorization? [duplicate]

Suppose in the future someone conjures a technique to (arbitrarily) quickly find the prime factors of arbitrarily large numbers, thus undermining the computational security of (as far as I am aware) ...
-1
votes
0answers
123 views

Division of a number in Paillier encrytion which yields decimal result

I am very new to start with Paillier encryption system. I have used the homomorphic nature of this scheme, which allows addition of two encrypted numbers. I was wondering is it possible to divide two ...
0
votes
0answers
46 views

Shor's algorithm: Similarities between exponent r and Carmichael's function

I'm trying to learn Shor's algorithm. In the explanation section on the Wikipedia article, there is a paragraph - The integers less than $n$ and coprime with N form the multiplicative group of ...
1
vote
0answers
104 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
878 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
408 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
136 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
218 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
67 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
852 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
119 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
185 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
63 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
58 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
638 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
177 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
753 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
84 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
119 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
258 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 ...
0
votes
0answers
71 views

What kind of Mathematics background do cryptographers have? [duplicate]

I now it is mostly based on numbers theory. But are there any other mathematics branches used there?
-1
votes
1answer
76 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
132 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
237 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 ...