Questions tagged [cryptography]

Questions on the mathematics behind cryptography, cryptanalysis, encryption and decryption, and the making and breaking of codes and ciphers.

Filter by
Sorted by
Tagged with
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 $...
user avatar
  • 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 ...
user avatar
  • 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? ...
user avatar
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 ...
user avatar
  • 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},...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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) ...
user avatar
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 ...
user avatar
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$ ...
user avatar
  • 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 ...
user avatar
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 (...
user avatar
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.
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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. ...
user avatar
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) ...
user avatar
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 ...
user avatar
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}$...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 \...
user avatar
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 ...
user avatar
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....
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 : ...
user avatar
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$. ...
user avatar
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-$...
user avatar
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 ...
user avatar
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) ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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'...
user avatar
  • 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 $$ $$...
user avatar
  • 225

1
2 3 4 5
36