Questions tagged [cryptography]
Questions on the mathematics behind cryptography, cryptanalysis, encryption and decryption, and the making and breaking of codes and ciphers.
1,909
questions
0
votes
1
answer
43
views
Prove that if $e.d \equiv 1 \bmod (p-1)(q-1)$ then it’s impossible to have $e.d \equiv 1 \bmod pq$
I am studying R.S.A. cryptosystem and here is the question that came to my mind. Let’s pick $p, q$ to be two primes and $n = p * q$. From that we calculate Euler’s totient function:
$$
\phi(n) = (p - ...
0
votes
0
answers
17
views
Finding slope of a given point on the elliptic curve given the points x and y coordinates
How to find the slope of a given point on the elliptic curve provided i have it's x and y coordinates without knowing how the x and y coordinate were formed.
The equation for the curve am looking for ...
0
votes
0
answers
17
views
Time to Find an Elementary Antiderivative of an Elementary Differential Form?
So, in encryption theory, a basic principle is that one has an operation that can be computed in a "forward direction" relatively quickly but for which computing in the "reverse ...
- 817
0
votes
0
answers
16
views
Testing a Pseudo-Random Number Generator Algorithm
I created a pseudo-random number generator that creates random bits from given numbers. For better visualization, suppose that we have inputs "a", "b", "ab", "abc&...
0
votes
0
answers
30
views
Probability of Generating an Acceptable RSA Public Key: Help Needed!
I trust this message finds you in good health. I am currently immersed in a cryptography project and seek guidance in comprehending the likelihood of generating a viable public key within the RSA ...
- 1
2
votes
0
answers
52
views
About calculating isogeny between two elliptic curves
I'm trying to understand Vélu formulas for calculating isogenies. I took an elliptic curve $E: y^2 = x^3 + 3x + 5$ over $GF(7)$. So I've got the following points on this curve:
\begin{equation}
\{\...
- 95
0
votes
1
answer
36
views
Binary multiplication in Galois Field GF(2^8)
I am working on a project (high school), and I need to explain the process of AES MixColumns for one of the parts.
I am trying to show an example of the matrix multiplication in MixColumns that uses ...
- 3
0
votes
0
answers
42
views
Are high-dimensional versions of NTRU cryptosystem more secure?
The basis for this question is a 1-dimensional NTRU cryptosystem.
After some literature inspection I have found out it can be also generalised into higher algebras: quaternions (QTRU) and octonions (...
- 239
0
votes
0
answers
25
views
ElGamal signature scheme problem and unsure whether my calculations are wrong or that's the answer.
Trying to solve problem with verifying a message through the ElGamal signature scheme and I end up getting two different values.
I'm given a prime number $p = 881$, $e_1 = 3 d = 60$, random value $r = ...
- 1
0
votes
1
answer
65
views
Clarification on Multiplication in $GF(2^3)$ vs. Boolean Algebra
While experimenting with finite fields, specifically $GF(2^3)$, I stumbled upon a puzzling situation when comparing multiplication operations to those in Boolean algebra.
Let's take two elements $A$ ...
- 15
1
vote
0
answers
48
views
What are the necessary and sufficient conditions for simplifying function iteration
Taking for example, suppose there are now many butterfly diagrams stacked to form a multi-layer network. Obviously, when each computing unit is linear, the entire network can be simplified using a ...
- 33
2
votes
1
answer
100
views
Show that this RSA encryption iterated $10$ times does not encrypt $x$
Let's say we have an RSA key of modulus $n = 383\cdot563 = 215629$ and encryption exponent $e = 49$. Suppose our encryption $E(x)=(x^{49})^{10}$ where we are iterating $x^{e}$ ten times. I want to ...
0
votes
1
answer
50
views
Is there an algorithm that uses prime numbers in symmetric encryption? [closed]
It is well known that there are algorithms developed for asymmetric encryption that take advantage of the fact that the product of two prime numbers cannot be factored in polynomial time. Usually, ...
0
votes
0
answers
22
views
Finding $m_1$ and $m_2$ (or $d_1$ and $d_2$ using RSA when $e_1$, $e_2$, $n_1$, $n_2$, $c_1$, $c_2$ are known, $e_1=e_2$ and $p_1=p_2$
I'm trying to obtain messages $M_1$ and $M_2$ using RSA under the following conditions:
There are two RSA asymmetric keys:
$p_1$ and $p_2$ are unknown, however we know that $p_1=p_2$
$q_1$ and $q_2$ ...
0
votes
0
answers
32
views
Shamir Secret Sharing
Can anyone please explain to me why we have such equations below in part b) and c)? They are the solutions to the questions, but I can't really understand why and how to get that. Many thanks.
==== ...
- 11
0
votes
1
answer
76
views
Can we formally prove that XOR operations 'cancel'?
Suppose I have two sequences of binary bits m1 and m2, and an
accompanying 'key string' K of bits with all three the same length.
Then if I define c1 and c2 as:
...
- 431
0
votes
0
answers
44
views
Finding an algorithm to factor $n$ given cube root $\mod n$
Let $p,q$ be unknown primes and $n=pq$.
Also let:
$p\equiv 4 \mod 9$
$q\equiv 4 \mod 9$
Imagine I have an "oracle" that takes cube roots $\mod n$. Find a probabilistic algorithm to factor $n$...
1
vote
0
answers
43
views
Are these two definitions of one-way function equivalent?
Here comes two definition of one-way function, the first one comes from wikipedia while the second one is by myself.
I'm curious about whether they are equivalent and have been considering for a long ...
- 11
3
votes
1
answer
76
views
Could you formulate a block chain as a category?
Relatively straight forward question I had after finishing a review of the ethereum yellow paper. How might one go about or is it even possible to formulate the general math behind a blockchain as a ...
- 31
1
vote
1
answer
43
views
Modulo composition confusion [duplicate]
In a cryptography lecture, I have run into a equation such that
$$y_i=e(x_i)=x_i+s_i(mod2)$$ $$x_i=d(y_i)=y_i+s_i(mod2)$$ where $e()$ means encryption and $d()$means decryption in Stream ciphers.
...
user1239778
0
votes
0
answers
29
views
Why is RSA encryption exponent always odd/never even? [duplicate]
I remember my professor mentioning that RSA encryption fails when $e$ is odd, but cannot seem to figure out why it is so, and can't find a proof in a textbook/online. I tried verifying it by proof-by-...
1
vote
0
answers
30
views
NTRU cryptosystem lattice reduction attack
I need help understand the attack on NTRU cryptosystem
https://en.wikipedia.org/wiki/NTRUEncrypt
For example:
Given Alice’s public key: q = 131 and h = 100. Suppose that Bob sends the encrypted ...
- 252
1
vote
1
answer
36
views
Coordinates after point multiplication not in elliptic curve.
When calculating $2P$ where $P = (7, 11)$ on the elliptic curve E: $y^2 = x^3 + x + 1 \mod 23$.
I get $$ \lambda = \frac{3 * 49 + 1}{2 * 22} = \frac{74}{11} \mod \ 23 = 10.$$
Then when I calculate $ ...
- 11
0
votes
0
answers
30
views
What does it mean that the distribution of a variable is well-defined?
In the proof of a lemma in a paper, the authors say "Observe the distribution of $\vec{d}$ is well-defined." What does it mean mathematically?
Here is the picture of the notation, lemma, and ...
- 141
3
votes
0
answers
73
views
A Mersenne number is never a Carmichael number
I am tasked with proving that all Mersenne composites (that is, composite numbers of the form $2^n -1$) are either always Carmichael numbers or never are.
Running some tests, I have found some ...
- 345
0
votes
1
answer
119
views
Finding key for Hill Cipher
Suppose a Hill cipher with block size 2 is given, with known plaintext and corresponding encryption
$E_K( ‘guns’ ) = ‘YGJC’$
What are the possibilities for the key $K$?
My initial thought was to setup:...
0
votes
0
answers
13
views
the hardness of Conjugacy Search Problem in matrix groups
I learned that the Conjugacy Search Problem is considered as a mathematically hard problem to solve and can be used for cryptography.
Conjugacy search problem: Let G be a non-abelian group. Let g,h∈G ...
1
vote
0
answers
56
views
Exact algorithms (e.g. in coding theory, cryptography) using the field of rational numbers
I noticed that most algorithms in coding theory or cryptography are based on the integers and some arithmetic results (e.g. RSA) or on the finite fields (e.g. Elliptic curve cryptography or BCH codes)....
- 451
1
vote
1
answer
54
views
(How) can two words differ in fewer places than the minimum distance?
I'm working on an unassessed course problem (which I paraphrase for conciseness),
Let $C$ be the code over $\mathbb{F}_5$ with generator and parity-check matrices
$$G=\begin{pmatrix}2&3&4&...
- 2,051
0
votes
0
answers
53
views
Given two public keys and $e$ to find a private key
I am taking a cyber security class recently. I was wondering if I was given two public keys, $n_1$ and $n_2$ (and $e$ the exponent)--how would one generate a private key for $n_1$? In this scenario, $...
- 11
1
vote
0
answers
29
views
Recommendations for Papers on LLL Algorithm
Asked a professor who does research in cryptography for a project opportunity, and he told me to go read about Lenstra-Lenstra-Lovasz or LLL algorithm. I read the following paper and found the topic ...
0
votes
1
answer
69
views
Can an algorithm prove that it produced its own output?
Apologies in advance for my ignorance. I am working on a research question in a different area, and it would be helpful to know the answer to the following question, or even a reference to any such ...
- 31
1
vote
2
answers
76
views
If $x^e \equiv y^e \pmod N $, is $x \equiv y \pmod N$ where $\gcd(e,\phi(N))=1$?
Let $x,y,e,$ $p$, and $q$ be any integers where $N= pq$ and $e$ is coprime to $(p-1)(q-1)$ . I am wondering whether $x^e \equiv y^e \pmod N $ implies $x \equiv y \pmod N$, and if so how to show this. ...
- 2,145
1
vote
0
answers
45
views
Ramanujan Graph, supersingluar isogeny graph [closed]
Given a prime $p$, the super-singular isogeny graph has about $\dfrac{p}{12}$ nodes and is a Ramanujan graph. Its distance is about $\log(p)$, First question what is the bound of distance? Second, for ...
- 81
-2
votes
1
answer
75
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?
- 79
-2
votes
1
answer
91
views
Why do we use prime numbers with RSA? [closed]
I coded a small example of RSA in Python. When filling p and q, I mistakenly put in two numbers that were not prime numbers. And ...
- 19
1
vote
0
answers
29
views
Distribution in the amount of roots of a randomised polynomial over the ring $\mathbb{Z}_{2^k}$.
I'm now trying to develop some protocols to work with cryptography over the ring $\mathbb{Z}_{2^k}$, and I tried to find a ring version of the Schwartz Zippel lema. The main idea is to work in a ring ...
- 108
0
votes
2
answers
57
views
Proof of correctness of RSA sufficient? [duplicate]
In a lecture I am taking the following proof for the RSA cryptosystem is given:
$m^{ed} \equiv m^{ee^{-1}} \equiv m^1 \equiv m \pmod N$
where $N = pq$; $p$,$q$ prime; $2 < e < \phi(N)$; $e$,$\...
- 249
0
votes
0
answers
50
views
Trouble detecting cyclic group order crossovers in elliptic curve additions
There's a problem in detecting whether the sum of public key addition has crossed the cyclic group order boundary
For this example, think of public keys $Pub$ as private keys $Priv$, (private scalars),...
0
votes
0
answers
32
views
Schnorr signature variant with sum c and k instead of multiplication
I am reading about Schnorr signature and I though what if we calculate response as $r = \alpha + c + k$ instead of $r = \alpha + c*k$? Will it make scheme more insecure? Are there any name for this ...
1
vote
1
answer
79
views
Show that $f(x)=x^2+2x-1 \in \mathbb{Z}_3[x]$ is irreducible over $\mathbb{Z}_3$. And find the elements of a finite field with 9 elements.
Show that $f(x)=x^2+2x-1 \in \mathbb{Z}_3[x]$ is irreducible over $\mathbb{Z}_3$. Using this fact construct a finite field $\mathbb{F}_9$ of $9$ elements. If $\alpha$ is a root of $f(x)$, then find ...
- 741
0
votes
1
answer
30
views
Show that $3x^2+A\ne 0$ if $y=0$ for a point on elliptic curve.
Let $(x,y)$ be a point on the elliptic curve $E$ given by $y^2=x^3+Ax+B$. Show that if $y=0$ then $3x^2+A\ne0$.
I have a graphical intuition for this. Since $$\frac{dy}{dx}=\frac{3x^2+A}{2y}$$
and ...
- 741
0
votes
0
answers
30
views
Given the shared key, find the decryption of cipher text.
I'm taking a course in Cryptography, and I came across this question:
Let Alice and Bob use Hill Cipher to encrypt the message $m$ as $km$ for $k\in \mathbb{Z}^*_{41}$. Let $G=\mathbb{Z}^*_{83}$ and $...
- 741
2
votes
0
answers
43
views
The number of integers less than x that have at least two distinct prime factors of bit size greater than one-third the bit size of x
Sander came out with a paper describing how to generate what he calls an RSA-UFO. Anoncoin then utilizes this and mentions that the paper proves that the probability that a randomly generated integer, ...
- 123
0
votes
0
answers
110
views
Find the generator matrix (block code) given the codewords
So I was given the following (6,3) block code with some unknown values marked with x:
format: index,(msg) -> (code word)
1 (0 0 0) -> (0 0 0 0 0 0)
2 (1 0 0) -> (0 1 1 1 0 0)
3 (0 1 0) ...
0
votes
0
answers
38
views
Derive an explicit expression for $P_e=P(\psi_1|\psi_2)P(\psi_1)+P(\psi_2|\psi_1)P(\psi_2)$
I am currently working with an exercise set about discriminating between two different quantum states. We consider a 2-dimensional Hilbert space expanded by $|\phi_1\rangle$, $|\phi_2\rangle$. The ...
- 259
0
votes
0
answers
95
views
Using Riemann-Roch Theorem to show every elliptic curve can be written as a plane cubic
I've been studying how to show that every elliptic curve can be written as a plane cubic through the book of Joseph H. Silverman "Arithmetic Elliptic Curves", the proof of proposition III.3....
- 147
0
votes
0
answers
41
views
Confusion of Generator point in it's Montgomery Form and Weierstrass Form for secp256k1
I am using GEC Module (https://github.com/HareInWeed/gec) to perform point operations on secp256k1. Here, the generator point is defined as below
...
0
votes
0
answers
25
views
Fiat-Shamir heuristic for the layperson
I am trying to understand the example given on this page:
https://en.wikipedia.org/wiki/Fiat%E2%80%93Shamir_heuristic
but the explanation says I need to be familiar with both multiplicative groups and ...
- 121
0
votes
0
answers
26
views
How complex is to solve subset-sum-problems using super increasing sequences with the following algorithm?
I'm writing about the Merkle-Hellman-Cryptosystem in my thesis, this uses subset-sum-problems (SSP) with super increasing sequences. The SSP is NP-complete, but the SSP consisting of super increasing ...
- 3