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

learn more… | top users | synonyms

0
votes
1answer
34 views

Confusion regarding computing Multiplicative Inverse Modulo P?

May be a silly doubt, please rectify my confusion regarding below problem: For concreteness assume $g=2, p=11, a=6$ and $x=9$ $$A = g^a \bmod p = 2^6 \bmod 11 = 9$$ $$X = g^x \bmod p = 2^9 \bmod 11 ...
2
votes
0answers
32 views

Is it possible to generate backdoored DH parameters?

I know it has been already asked and answered whether it's possible to generate weak DH parameters. But "recentely" we experienced the Logjam attack, which makes use of the pre-computation ...
0
votes
1answer
38 views

Algorithm for factoring a number $n$ of a specific form given $n$ and $\varphi(n)$

Given the natural number $n$, which is in the form $p^2 \cdot q^2$ with $p$,$q$ prime numbers. Also $\varphi(n)$ is given. Describe a fast algorithm (polynomial time) that calculates $p$ and $q$. ...
6
votes
1answer
127 views

What if the p and q used in keys generation of Pailler cryptosystem are composite?

I've seen a few implementations of Paillier cryptosystem that uses probable primes to choose $p$ and $q$. Assuming that a keypair is generated with $p$ and $q$ that are coprime and that $pq$ is ...
3
votes
2answers
98 views

What is the difference between the standard representants of $\mathbb Z/q\mathbb Z$?

The symbol $\mathbb Z/q\mathbb Z$ (given that $q$ is prime) represents the prime field $\mathbb Z_q$. Basically, the elements of this field are represented by $\{0, 1, \dots, q-1\}$, let's call this ...
0
votes
2answers
56 views

How to compute two EC point multiplication?

I would like to know how to compute multiplication of two valid EC points over a curve E with generator G. i.e. Given only P and Q points then how to compute R = P * Q where $P = p G$, $Q = q G$ and ...
3
votes
1answer
244 views

How is information disclosed by modular multiplication?

Consider the case that $c = a \cdot b \mod p$ where $p$ is a known prime and $0 < a < p$ and $0 < b < p$ are unknown integers numbers. Furthermore, some bits on the value of $c$ are ...
2
votes
2answers
68 views

Is it hard to recover $p$ from $k \phi(p)$?

Given $k\phi(p)$, is it hard to recover $p$? Here, $p$ is a large prime, $\phi(\cdot)$ is Euler's totient function and $k$ is an unknown integer. Or what's the complexity to recover $p$ from $k ...
3
votes
1answer
90 views

Non adjacent form of an integer is unique

I have tried to look up the proof for NAF (Non-adjacent form) being unique for every integer, but as far as I have seen, textbooks only mention it as a property of NAF, but no proof is given. Also I ...
1
vote
2answers
128 views

Is computing roots moduli a composite $N$ a hard problem without knowing the factorization of $N$?

Suppose that we are given $\mathbb{Z}_{N}$ and an element $x^u \in \mathbb{Z}_{N}$ with $u \in (0,l]$ where $l$ is the bit-size of $N$. Is it difficult to recover $x$ by knowing $u$ without knowing ...
1
vote
1answer
51 views

In a additive group is it hard to calculate $bg$ given $ag, g, abg$

The ECDH problem defined that given $g,ag,bg$ it is difficult to calculate $abg$. But it is also difficult to calculate $bg$ given $ag,g,abg$. where $g$ is generator and a,b are elements of group.
0
votes
1answer
56 views

Applications of GF(p) polynomials

A Galois field of the type $GF(p)$, where $p$ is prime, is normally expressed as the ring of integers modulo $p$. If my understanding is correct, it is also possible to represent its elements as a ...
-1
votes
1answer
129 views

subgroup of quadratic residue

if a number is said to be a subgroup of a quadratic residue of Z∗p, can I affirm that it is a generator of a cyclic group ? ie, say i am looking for a number which is an element of order q in Z*p, ...
0
votes
1answer
97 views

Prime Numbers in Discrete Log

I am implementing a security protocol based on discrete log. I came across the equation $p = kq + 1$. Understand that based on number theories that both $p$ and $q$ should be large enough to be ...
-1
votes
1answer
83 views

What does $\mathbb Z_p^*$ contain?

I have a prime $p = 7$ and was tasked to select a random value in $\mathbb Z_p^*$ in my signature scheme. What does the full range of $\mathbb Z_p^*$ contain in this case? Is it $\{0...7\}$ or ...
1
vote
1answer
269 views

How costly is to find millions of large prime numbers for RSA?

Consider I need to assign a large distinct prime number to each element in a large set. This must be deterministic so the function always gives me the same prime to the same value. What is the most ...
1
vote
1answer
187 views

Equal length of primes in paillier cryptosystem

In the key generation step of paillier cryptosystem , In order to satisfy $\gcd(pq,(p-1)(q-1))=1$ , we can take equal length primes. Instead of taking(length as parameter to generate $p,q$) equal ...
2
votes
2answers
208 views

Given $g$, $b$, $g^{ab}$, is finding $g^a$ a hard problem?

As in the title, given $g$, $g^{ab}$ are big elements in a prime group $Z_p$ and $b$ in prime group $Z_r$ ($p > r$, $g$ is one generator of $Z_p$). $a$ is unknown and also in $Z_r$, is finding ...
1
vote
1answer
122 views

Non-commutitive and nonassociative algebraic structures in cryptography

Are there any cryptographic algorithms or primitives that have been developed and studied that make use of non-commutative or non-associative algebraic structures such as quaternion integers or ...
1
vote
0answers
40 views

What constitutes a “description of B” for probabilistic encryption as defined in Cryptology 6.3.4?

On page 21 of the Rivest's Cryptology chapter, he defines a trapdoor predicate as a boolean function for which it is easy to choose an x such that ...
0
votes
1answer
162 views

RSA, finding p,q [duplicate]

If the public key $(e,n)$ and the private key $(d,n)$ are known, what is the easiest way to find the primes $p$ and $q$? When $n$ and $\phi(n)$ are given this is easy to solve. But I can't manage it ...
4
votes
1answer
177 views

Is the strength of RSA over quadratic or other cyclotomic fields as strong as over the integers?

If we assume the strength of RSA is based on the difficulty of factoring (which I know we can't guarantee) and we compose the modulus of some other quadratic ring that is a unique factorization domain ...
0
votes
1answer
97 views

Existence of a map $\phi:\mathbb{Z}_{N^2}^* \mapsto \mathbb{F} $

Is there a map between the group of $\mathbb{Z}_{N^2}^*$ where $N$ is a composite number , a product of two equal size secure prime numbers $p$ and $q$ and a finite field $\mathbb{F}$, such that for ...
0
votes
1answer
130 views

What are alternatives to number theory based crypto? [closed]

Quantum crypto,lattice based crypto, Neurocryptography and cellular automata based cryptography are alternatives to number theory based crypto. I need to know what are the other hard problems like ...
1
vote
1answer
121 views

Modular exponentiation with Chinese Remainder Theorem

I'm learning modular exponentiation with Chinese remainder theorem. I found a great answer from below How can I use eulers totient and the chinese remainder theorem for modular exponentiation? But I ...
5
votes
5answers
514 views

Is there a technique to confirm that a given large integer value is a product of two primes?

Given a list of 2048 bit integer values in which one or few 2048 bit integer values may be product of two prime numbers and other values may be just 2048 bit odd integers numbers. My question is - ...
3
votes
2answers
314 views

Breaking a PRNG Scheme

Assume the following scheme for a PRNG generating decimals in [0,100) Given a message and a key, compute tag := HMAC512(message, key). Take the first 5 hexadecimal characters of the tag. If the ...
2
votes
1answer
152 views

Efficiently computing the neutral element in a ring isomorphic to Z/NZ?

Edited to clarify question So my question is whether anyone knows of an efficient way to compute the neutral element (I'm gonna call it 1, but the operation doesn't have to be multiplication) in an ...
3
votes
2answers
91 views

Possible to check if $a \in \mathrm{QR}_n$?

It is possible to check $a \in \mathrm{QR}_p \text{ iff } a^{(p-1)/2} \equiv 1\ (\bmod\ p)$ if $p$ is a prime. $n$ is a large RSA modulus. Is it also possible to check if $a \in \mathrm{QR}_n$ if the ...
5
votes
1answer
1k views

AES mixcolumn stage

I'm studying AES, and am having problems with the "mixcolumn" stage. I read about finite fields, but I still don't know. How do I construct $GF(2^8)$? ...
2
votes
1answer
858 views

ECC - Point Addition/Point Multiplication

So I have a very beginner-esque knowledge of ECDSA and I'm trying to write something in python to take a private key and output the public key (Basically from what I understand just trying to do the ...
5
votes
1answer
192 views

Is it possible to fool Miller-Rabin test?

It is well known that it's possible to fool Fermat test with Carmichael numbers. But, is it possible to deliberately fool many-rounded Miller-Rabin test by constructing some special number without ...
4
votes
4answers
434 views

Where does the $\varphi(n)$ part of RSA come from?

$e d \equiv 1 \pmod{\varphi(n)}$ Where does the $\varphi(n)$ part come from? How did the inventors of RSA arrive at $\varphi(n)$?
-2
votes
1answer
117 views

What parts of number theory does the RSA algorithm use?

It is said that the RSA algorithm uses number theory. What parts of number theory does it use? I know it uses modular arithmetic and Euler's totient theorem and function. Is that all?
6
votes
0answers
143 views

Has the distributed project “Number Fields @ Home” project benefited cryptography in any meaningful way?

Is there any new understanding, property, or knowledge that has come from the Number Fields @Home distributed computing project? Has any outcome advanced the study of cryptography, or altered ...
2
votes
2answers
220 views

Need 32-bit mixing function that has perfect avalanche between octets

for my hobby tinkering project, I need a mixing function that takes 32-bit input and has 32-bit output (and will, most likely, run in a 32-bit C environment) and the following property (independent of ...
1
vote
0answers
106 views

$\phi$ function in Dual_EC_DRBG

I am trying to understand the operation of the Dual_EC_DRBG. I'm reading the formal specification (SP 800-90) and can't seem to find a definition of the $\phi$ function used throughout the definition ...
0
votes
1answer
104 views

Quadratic Residues in identification setting

Suppose Alice has two primes $p$ and $q$ such that $p\equiv q \equiv 3 \pmod 4$. $n=p\cdot q$ is part of her certificate to identify her. A party say Bob, sends her a random quadratic residue ${}\bmod ...
3
votes
1answer
267 views

What are the possible cryptographic implications of Zhang's proof of the Twin Prime Conjecture?

Earlier this year, Yitang Zhang published a proof of a weakened form of the Twin Prime Conjecture. I'm wondering if any of the new mathematical machinery he developed has uses in cryptography or could ...
1
vote
1answer
108 views

Question about Fermat's little theorem

Why is $g^e \mod p = g^{e \mod (p-1)} \mod p$ if p is prime. I don't get it. It follows from Fermat's little theorem.
0
votes
2answers
163 views

Key Refresh in Diffie-Hellman

Assume the case, that two participants have agreed on a key $K=g^{ab} \mod p$ via Diffie Hellman. I have the need to change the key every now and then. The first idea I had was to simply initiate a ...
8
votes
3answers
411 views

Building a hard to factor number without knowing its factorization

It is possible to find an efficient algorithm for constructing a provably hard to factor number $N$, together with a witness that shows that it is indeed hard to factor. EDIT, since it was not clear: ...
1
vote
3answers
219 views

Which area of Maths should I pursue?

I would like to know which area of Mathematics would be most beneficial to cryptography. Surely Algebraic Number Theory and maybe to a lesser extend, Elliptic Curves, are closely linked to ...
1
vote
1answer
571 views

Algorithm for proving Carmichael numbers

I have an application for determining if a number is a prime or not, currently I'm getting a random number, then doing the Fermat primality testing to find out if the number is probably prime (so this ...
7
votes
2answers
510 views

Given a message and signature, find a public key that makes the signature valid

Given a message $M$ and a signature $S$, is it feasible to find a RSA public key $(n,e)$ such that $S$ verifies as a valid signature on $M$ (using this public key)? What if we're given one public key ...
2
votes
1answer
231 views

How did they factor RSA-704?

I don't understand the 'Wiedemann algorithm' works. Can someone explain the factoring of RSA-704 in an easy way?
12
votes
1answer
501 views

Do recent announcements about solving the DLP in $GF(2^{6120})$ apply to schemes proposed for cryptographic use?

A recent paper by Göloğlu, Granger, McGuire, and Zumbrägel: Solving a 6120-bit DLP on a Desktop Computer seems to "demonstrate a practical DLP break in the finite field of $2^{6120}$ elements, using ...
1
vote
1answer
369 views

What does $(\mathbb{Z}_n^*)^2$ mean?

In a paper they write once, $(\mathbb{Z}_n^*)^2$. Is this the group of quadratic residues or is it something else? Here the theorem: Under the strong RSA assumption, given a modulus $n$, along with ...
6
votes
1answer
439 views

Prove that textbook RSA is susceptible to a chosen ciphertext attack

Given a ciphertext $y$, describe how to choose a ciphertext $\hat{y} \neq y$, such that knowledge of the plaintext $\hat{x}=d_K(\hat{y})$ allows $x=d_k(y)$ to be computed. So I use the fact that the ...
2
votes
1answer
69 views

Comprehension question on a signature protocol based on the RSA assumption

We have the following two-party protocol between Alice and Bob. Alice sends messages $m_1, m_2, \ldots \in_R \mathbb{Z}_n^*$ to Bob and Bob signs these values by calculating $v_1, v_2, \ldots \in_R ...