All Questions
Tagged with cryptography number-theory
334
questions
1
vote
2
answers
41
views
Fermat's last Theorem and elliptic curve cryptography
AFAIR, elliptic curve cryptography became popular soon after Fermat's last Theorem had been proven. Is it just a coincidence, or some important cryptographic properties of elliptic curves follow from ...
0
votes
0
answers
31
views
How can I be certain of the existence of elliptic curves of certain order when the parameter a is fixed?
My question came up while researching an attack on Elliptic Curve Cryptography (described in Computer Security - ESORICS 2015.
I'm given an elliptic curve $E$ defined by $y^2=x^3+ax+b$ over the finite ...
0
votes
1
answer
107
views
Find all pairs of keys $(a, b)$ for affine ciphers.
The question is as follows:
Find all pairs of integer keys $(a, b)$ for affine ciphers for which
the encryption function $c = (ap + b) \bmod 26$ is the same as the
corresponding decryption function.
...
-2
votes
1
answer
110
views
Existence of the shortest vector in a lattice [closed]
I am studying integer lattices in $\mathbb{R}^n$. I know that since there are no accumulation points in the lattice, the shortest vector always exists. Is there any way that one could prove it?
0
votes
1
answer
47
views
Algorithm for determining whether $\gcd$ of two polynomials is unequal $1$, for use in Schoof's algorithm and $ECC$
I'm currently working on a $ECC$ Project. In the implementation of Schoof's Algorithm we need to check, if the following property holds for high order q:
$$\gcd\left(x^q-x,x^3 + Ax +B\right) \neq 1$$
...
0
votes
1
answer
144
views
Pollard's Rho Algorithm and Floyd's Cycle-Finding
I'm doing a project on Pollard's Rho algorithm, and after lots of readings, I still am very confused about this one part.
I understand why there's a pseudorandom sequence, and I understand why it must ...
1
vote
3
answers
129
views
Why are there always two primes between $2^n$ and $2^{n+1}$?
In a cryptographic lecture we just assumed that this statement holds. In particular, we said for a fixed length of bits one can always find two primes, that have the same length in binary ...
0
votes
1
answer
115
views
Discrete log over a prime
I have a prime $p$ such that $p-1=2 p_1p_2$ such that $p_1$ has $200$ digits in base $2$ and $p_2$ has 50. I want to find discrete logarithm of $a^b =c \pmod p$. That is I want to find $b$ given $a,c, ...
1
vote
0
answers
29
views
Reduced $O_K$-basis for a free $O_K$-module
Background:
let $L \subset \mathbb{Q}^n$ be a lattice (i.e. a finitely generated $\mathbb{Z}$-module). Then $L$ has a reduced basis, that is, a $\mathbb{Z}$-basis $v_1, \dots, v_r$ satisfying $\prod_{...
1
vote
1
answer
320
views
Finding one of the two prime factors in RSA from the above equations, if we know what the c1,c2,e1,e1,N are.
There is a problem i am trying to solve on RSA.
We have two ciphertexts which have been encrypted with different public exponents e, but share the same modulus N.
Assume that the c1,c2,e1,e2,N are ...
3
votes
0
answers
22
views
If $f(m)\equiv 0\pmod{N}$, and $\beta$ is a root of $f$ in an extension field, why is $m\equiv\beta\pmod{N}$ in $\mathbb{Z}[\beta]$?
In the set up for the number field sieve, to factor some large $N$, one first takes a monic irreducible $f(x)\in\mathbb{Z}[X]$ and finds some nonzero integer $m$ such that $f(m)\equiv 0\pmod{N}$ in $\...
2
votes
1
answer
3k
views
R.S.A. Encryption: find $d$ if we know $n$ and $e$
If an R.S.A. system has $n=55$ and the encryption key is 13
Do I choose $p$ and $q$ as 5 and 11
so $n = 5 \times 11$
and then $\varphi(n) = (5-1) \times (11-1) = 40$
Is this the correct start? Will ...
0
votes
1
answer
173
views
Deciphering XOR-encrypted text with frequency analysis.
I know nothing about cryptography, so I appreciate simple explanations.
Assume each letter of an English Alphabet is represented by a 5-bit string.
I read that XOR-encrypted text can be deciphered ...
0
votes
1
answer
161
views
xor values of character and space vs xor value of character and character
How do i prove that xor of character and character is always less than 64 while xor of a space and a character is greater than equal to 64 .
NOTE :that all english characters have ascii in [64, 127] ...
1
vote
0
answers
78
views
How to find square root mod N by knowing N factorization [duplicate]
Suppose we know $p$ and $q$ two prime number, is there a way to find $x$ to satisfy this equation for $x$:
given $a$ and $n$ where $n =pq$
find $x$ such that
$x^2=a \bmod n$.