Questions tagged [cryptography]
Questions on the mathematics behind cryptography, cryptanalysis, encryption and decryption, and the making and breaking of codes and ciphers.
1,785
questions
0
votes
0
answers
79
views
Proving an encryption isn't secure based on RSA
I need help proving this encryption method isn't secure (based on RSA).
We have:
Encrypter pick $p$, $q$ both very large primes
Encrypter picks $g,r_1,r_2$ all integers (random) -> they calculate $...
- 39
0
votes
0
answers
13
views
Finding the original logistic map, given a binary sequence
Logistic maps can be used to generate a pseudo random sequence of binary digits. Here is an article.
But is there a method to reverse this?
Q1 : Given a sequence $b_0 b_1 b_2 ... b_n$, is it possible ...
- 145
-3
votes
0
answers
29
views
What form of citation should I be using for my mathematics research paper? [closed]
I am wondering what form of citation I should be using for my undergraduate final research paper on modern cryptography. I would prefer to have no footnotes. Does anyone have any recommendations?
...
2
votes
2
answers
93
views
Finding 1 solution of $(x^3 + ax + b) \bmod p = 0$
I am writing unit-tests for an elliptic curve implementation (secp256r1 / prime256v1) and need to find a curve point with $y = 0$ to reach coverage for an edge case (special handling of curve points ...
- 21
1
vote
0
answers
20
views
Invertible submatrices in matrices of a special form
Suppose you are given an ordered sequence consisting of $n$ pairs of length-$N$ bit vectors (i.e., each entry in each vector is $0$ or $1$), say
$$(b_{0,0},b_{0,1}),(b_{1,0},b_{1,1}),\ldots,(b_{n-1,0},...
- 11
0
votes
0
answers
13
views
Why can we perform the following simplification in the Diffie-Hellman problem? [duplicate]
I essentially have the same exact question as this one: Diffie Hellman Problem, which unfortunately doesn't have any good answers that clear up my confusion. There is one answer that is highly ...
- 2,814
3
votes
1
answer
38
views
Justifying a randomization technique for efficiently checking equalities in a prime-order group
In cryptography papers, I have seen a technique used to confirm that two equalities hold in a group that requires performing only a single computation in the group. This is apparently more efficient ...
0
votes
0
answers
73
views
Assuming secp256k1 curve and given fixed (but random) $h$ and $d$ values, is it possible to calculate a $k$ such that $h\equiv(k\,G)_X\,(k-d)\pmod n$?
For generator point $G$ in the secp256k1 curve, I want to find a value $k$ such that:
$$h\equiv(k\,G)_X\,(k-d)\pmod n$$
where $n$ is the group order, and $(k\,G)_X$ indicates the x-coordinate (mod n) ...
1
vote
0
answers
19
views
Any recommendation for explanations for the verification key in ZK-SNARK?
I've read dozens of articles that are not math-heavy and got a pretty good grasp on the general idea of ZK-SNARK but I have not found many good articles on verification keys. Wonder if anyone can ...
- 113
3
votes
1
answer
66
views
A property of the convergents of the continued fraction expansion of a rational number
I'm looking for a proof of the following result (theorem 6.14 of the book Cryptography. Theory and practice by Paterson and Stinson):
Theorem 6.14 Suppose that $\text{gcd}(a,b) = \text{gcd}(c,d) = 1$ ...
- 366
1
vote
1
answer
57
views
Point on elliptic curve that is torsion over algebraic closure
Say I have an elliptic curve $E: y^2 = x^3+4$ over $\mathbb{F}_{7}$. I want to find an $7$-torsion point in $\overline{\mathbb{F}}_7$ which is not in $\mathbb{F}_7$. How do I do that?
The $n$-torsion ...
- 406
0
votes
1
answer
38
views
Is Elliptic Curve Cryptography (ECC) used for key exchanges or encryption?
I understand how ECC works as an alternative to Diffie Hellman key exchange, but is ECC also used to encrypt information? If not, why is the strength to key size ratio of ECC always compared to RSA (...
0
votes
1
answer
47
views
Time complexity to compute f(k). [closed]
Suppose that $f(x)$ is polynomial, over finite field, of degree $n$. What is the time complexity to compute $f(k)$ for a given $k$?
It would be a great help!
Thank you.
- 13
0
votes
0
answers
32
views
Is it possible finding RSA key with only CRT exponents and a prime factor?
I am learning more RSA and I am facing with this problem.
I have given dp and calculated dq that:
$d \equiv dp (mod (p-1))$
$d \equiv dq (mod (q-1))$
Therefore, now I have a public exponent $e$, a ...
0
votes
2
answers
36
views
When does $B^x \equiv B^{2^{2^i}}\ (\textrm{mod}\ N)$ imply $(B^x)^x \equiv B^{2^{2^{i+1}}}\ (\textrm{mod}\ N)$
If $B^x \equiv B^{2^{2^i}}\ (\textrm{mod}\ N)$, under what conditions must it be true that $(B^x)^x \equiv B^{2^{2^{i+1}}}\ (\textrm{mod}\ N)$?
We can take for granted that $N$ is the product of two ...
- 103
0
votes
0
answers
42
views
RSA signature security
Let m be a message that the attacker Eve wants to sign with RSA signature scheme and with public key (n,e) and private key d.Suppose Eve can compute the signature of any other message such as m1 where ...
- 1
0
votes
1
answer
113
views
Is XOR distributive over any operations?
Given (A ^ C) * (B ^ C) = y where ^ is equivalent to XOR and * is equivalent to some ...
- 163
0
votes
0
answers
33
views
How to read algorithms based or non theorem-proof type textbook
In general, most mathematics textbooks I read are formatted in the introduction, lemma, theorem, proof, corollary, and examples format. For these kinds of textbooks, I would generally ponder and try ...
- 344
0
votes
0
answers
19
views
Private-key encryption scheme with indistinguishable encryptions in presence of eavesdropper.
I want to prove the following statement:
There is a private-key encryption scheme that has indistinguishable encryptions in the presence of an eavesdropper, but not indistinguishable multiple ...
- 207
1
vote
1
answer
127
views
Can't Solve Monoalphabetic Cryptosystem
I've stumbled across the following Monoalphabetic Cryptosystem question in Thomas Judson's book on Abstract Algebra (http://abstract.ups.edu/aata/exercises-crypt.html).
Assuming that monoalphabetic ...
- 25
0
votes
1
answer
112
views
Discrete Logarithm Problem as Period finding of a function
The discrete logarithm problem (DLP) : Find $b$ knowing $s,a$ and $p$ such that $$b=a^s\mod p$$
where $p$ is a prime number and $a$ is a generator of the group defined by $p$.
It is stated that the ...
- 6,895
1
vote
1
answer
76
views
How to reduce Hilbert class polynomial roots and complex j-invariants into finite fields
In PhD thesis "Cryptographic Schemes Based on Isogenies" by Anton Stolbunov on page 16, there are reductions of $\eta_i$, where $\{\eta_1, \dots, \eta_6\}$ are the roots of the Hilbert ...
- 13
0
votes
1
answer
53
views
Need help with notation used in McCallum-Relyea key exchange explanation
I want to better understand the McCallum-Relyea (MR) key exchange used in software called Clevis and Tang. (I'm an IT person, please excuse me for being mathematically not very precise.)
It is related ...
- 103
0
votes
0
answers
62
views
Evaluation of a polynomial over the finite field $\mathrm{GF}\left(2^{8}\right).$
I am trying to make a program that, among other things, considers a polynomial $p$ whose coefficients are elements of $\mathrm{GF}\left(2^{8}\right)$ and shows the user the graph of that polynomial. ...
- 43
0
votes
0
answers
64
views
Is there a group isomorphism between finite (abelian) groups where one can prove that the inverse has no analytically closed form?
In the case of the discrete logarithm (with the application of elliptic curve cryptography that maps a finite cyclic group to the cyclic subgroup of the elliptic curve defined by the generator point) ...
- 101
0
votes
1
answer
46
views
Crack RSA by using user signatures
Lets say I have a secret $s$ that is encrypted with a public key $(N,e)$. We know $e=35567$. However we don't know $N$.
We can ask the user to sign any message $m$ with his private key $(N,d)$ _ of ...
0
votes
0
answers
71
views
$n=s^2-t^2$ how many values can $s$ take?
Let's say we have $n=pq$ with $p,q$ prime. We can write $n=s^2-t^2$ for some whole numbers $s,t$.
Now prove that if $q<p\leq (1+\epsilon)\sqrt{n}$ then $s$ has at most $\frac{\epsilon^2}{2}\sqrt{n}$...
- 1,406
1
vote
1
answer
52
views
Can form of elliptic curve digital signature equation be simpler?
I am curious why equations for signing/validating with ECDSA have forms they have. Is it possible to use simpler equation that have same properties.
For example, this is an equation I found in the ...
0
votes
1
answer
77
views
I want to find primes $p$ where $p-1$ is smooth [closed]
I'm using the Pollard's $p-1$ method but for some numbers this method won't work.
For example for: $n = 436916347656251$.
$$n - 1 = 2 \times 5^{10} \times 7^5 \times 11^3$$
But Pollard's algorithm ...
1
vote
1
answer
31
views
How to prove that the derivatives of bent functions are balanced? [closed]
Function $F:\mathbb F_2^m\rightarrow \mathbb F_2^n$ is bent iff
$$ v \cdot F$$ is bent for all nonzero $v\in \mathbb F_2^n.$
Why is this equivalent to saying $F$ is bent iff $$D_a F = F(x)+F(x+a)$$ is ...
- 51
0
votes
0
answers
21
views
Can you derive the public key from a PGP encrypted message without knowing the content of the message?
I am working on a system to transfer short messages while obfuscating the intended recipient.
In essence, it combines many messages encrypted using PGP, and periodically publishes a file containing ...
8
votes
1
answer
355
views
How can one mathematically compute the security level of a human computable password schema?
Introduction
As technology advances, cryptographers are developing improved techniques for encoding information. While these techniques are becoming incredibly efficient for computers to perform, I am ...
user905694
4
votes
1
answer
172
views
Permuted Hamming distance
Suppose Alice wants to send a message to Bob, they agree on a $n$ letters alphabet $\Omega = \{a_1, \cdots, a_n\}$ and they both agree on a shared secret $\omega=\omega_1 \cdots \omega_m$ $\omega_i \...
- 51
1
vote
0
answers
108
views
Given a fixed hash value (h) and private key (p), is it possible to find a nonce (k) that fits the following equation in ECC mathematics?
Assuming secp256k1 curve and ECDSA parameters, I'm trying to see if there's a way to solve for $k$, where:
$k = {-h\over r} -p$, where $k$ is the ECDSA nonce, $p$ is the private key, $h$ is the hash ...
1
vote
0
answers
48
views
Would encrypting a message twice with RSA with different keys be more secure that once?
This was a practice problem for a class. The class is over now and I never solved it, so I thought I'd ask here.
Let's ignored the fact that adding extra security to single textbook RSA is unnecessary....
- 23
1
vote
1
answer
50
views
ElGamal same private and random key attack
I'm having difficulty understanding this.
Consider two messages are encrypted using the same cyclic group order $q$, generator $g$, private key $x$, and random parameter $y$.
The attacker knows a ...
- 23
0
votes
0
answers
19
views
How unique is this generated key?
I am building a small app. I want to generate a random and unique key for each user. If this thing takes off, I might have millions of users! [Coincidentally, this happening is about 1 chance in many ...
1
vote
0
answers
27
views
Show that a shift cypher is perfectly secure..
Using the formula $$ P(X =x|Y =y) = \frac{ P(X =x)∗\sum{_{x\in D_k(y)}}{P(K =k)} }{\sum{_{k|y \in C(k)}}P(K =k)∗P(X =D_k(y)). } $$ to show is that if all 26 keys $z$ are equally probable, the ...
- 21
0
votes
0
answers
92
views
How easy is it to break this encryption system a buddy of mine and I just discovered?
This is gonna take a little bit of background to explain, so here goes:
In base $11$, we have $11$ numerals to form numbers: $0, 1, 2, 3, 4, 5, 6, 7, 8, 9$, and since there is no single symbol ...
- 6,047
0
votes
0
answers
28
views
Does ElGamal cryptosystem require the Decisional Diffie-Hellman to be hard?
I've been reading about the ElGamal cryptosystem in the book An introduction to mathematical cryptography (chapter 2.4). It's stated that this cryptosystem requires the Diffie-Hellman problem to be ...
- 123
4
votes
1
answer
58
views
Question on Chernoff bound type probability argument.
The following result was given in the research article (claim 6) and no justification was provided for the proof. I have presented the claim in simple terms below. Basically, I want to understand what ...
- 1,487
0
votes
1
answer
69
views
Using the extended euclidean algorithm to crack LFSR
Question
I am having trouble cracking an LFSR using the Extended Euclidean Algorithm (EEA).
The problem comes as follow, let say we have the following LFSR :
...
0
votes
0
answers
31
views
Craking RSA with small exponents using polynomials
Alice is sending a message $m$ (after encrypting it to $c$) to Bob. Later she sends the message $m+r$ (after encrypting it to $c'$) to Bob. Eve is listening. She knows that Alice sent $m$ then $m+r$. ...
1
vote
0
answers
25
views
Prime $k-$tuples in cryptography
I have been studying $k-$tuples of primes and the Hardy-Littlewood conjecture for a few months, so far I have not found a specific application of these in cryptography. is there a way to use $k-$...
- 845
0
votes
2
answers
33
views
How many password combination at least two different letters?
Let's consider a system that requires 9 character long password. and there are 0~9, a-z, A-Z and at least 2 different categories in the 9 characters' password.
I saw other questions with "at ...
- 21
0
votes
0
answers
49
views
Likelihood of 2 being a liar in Miller Rabin test for large number (e.g. 1000+ bits)
I have written some working code to generate RSA key pairs using the Miller-Rabin primality test. All of the generated keys pass the openssl rsa -check function, meaning that (among other things) ...
0
votes
0
answers
24
views
Algorithm that solves a system of linear equations over finite fields when a parameter is needed
I was reading Kipnis' and Shamir's paper on Cryptanalysis of the HFE Public Key Cryptosystem by Relinearisation and I wanted to implement the example at the end in Octave without using any additional ...
- 1
1
vote
1
answer
25
views
How to find $a$ in $c \equiv b^{\textstyle\alpha^{\textstyle a}} \bmod N$ with $N = (2p_sp_b+1)(2q_sq_b+1)$ and $\alpha = (2p_bq_b)^2 \bmod \phi(N)$?
We also know the cycle length $L_c$
$$|\{\forall a: b^{\textstyle\alpha^{\textstyle a}} \bmod N\}| = p_{sf} \cdot q_{sf} = L_c$$
with $p_{sf}$ and $q_{sf}$ prime factors of the safe primes $p_{s}$ and ...
- 225
1
vote
1
answer
46
views
Construction of a recurrence sequence with given period
I want to construct a binary recurrence sequence which has period 1023. Moreover, it shouldn't have pre-period.
Can anyone help me with the procedure? I truly have no ideas where to start.
Also, I don'...
- 165
2
votes
1
answer
84
views
Sequence $x\mapsto x^a$ cyclic in 3 directions: $s_0^{b^ic^jd^k}\bmod N$. How to find member $ijk$ if projection to 1D not possible due mixed factors
Summery:
Can we determine $i,j,k$ for $s_{ijk}$
$$s_{ijk} \equiv s_0^{\beta^i\gamma^j\delta^k}\mod N$$
$$N = P\cdot Q \cdot R$$
$$P = 2\cdot p \cdot p_{big} +1 $$
$$Q = 2\cdot q \cdot q_{big} +1 $$
$$...
- 225