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

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 ...

0
votes
1answer
49 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
171 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
37 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
52 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
101 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", "...
3
votes
1answer
50 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
46 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
877 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
68 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
54 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
207 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
50 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
60 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
42 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
166 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
81 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
63 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) ...
0
votes
0answers
92 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
44 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
62 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
538 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
0answers
51 views

Can we determine which RSA public key will have the smallest corresponding Private key (without knowing ϕ(N))

Is it possible to determine or estimate for which value of public key, the corresponding private key will be a small number? (besides 1) without the knowledge of the ϕ(N).
0
votes
1answer
264 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 ...
0
votes
0answers
38 views

Average-case hardness of computational diffie-hellman problem

One of the main advantages of lattice-based cryptography is security is based on worst-case hardness i.e., construction based on lattice problem implies if we break the construction, then any instance ...
2
votes
1answer
112 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
163 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
61 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
779 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
100 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
181 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
61 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
54 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: ...
0
votes
1answer
246 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
150 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
690 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
67 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
78 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
85 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
103 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
216 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
61 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
123 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
175 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
106 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
52 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 ...
0
votes
0answers
180 views

Compute Modulo exponentiation with prime powers

The problem is to find x such that $$x = M^d \mod p^2$$, where M and d are large numbers, and p is a large prime. Ideally we only want to compute $M^d\mod p$ and then use the result to further ...
1
vote
1answer
105 views

New Improved Probabilistic version of RSA

On the 2nd page of "New probabilistic public-key encryption based on the RSA cryptosystem" by Roman'kov (PDF), at last it says Alice can find "f" of order "l" with least probability of (1-1/l). I ...
1
vote
2answers
161 views

Get $a$ such that quadratic residue has a solution (Rabin)

My task is to implement Rabin signature. I have trouble with choosing padding a such that $$x^2 \equiv a \pmod n$$ has a solution. In that context, $n=p\cdot q$ is composite, where $p$ and $q$ are ...