Questions tagged [cryptography]
Questions on the mathematics behind cryptography, cryptanalysis, encryption and decryption, and the making and breaking of codes and ciphers.
1,922
questions
1
vote
1
answer
32
views
AES S-box as simple algebraic transformation
The next matrix represents the Rijndael S-box according to wikipedia and other sources
$$\begin{bmatrix}s_0\\s_1\\s_2\\s_3\\s_4\\s_5\\s_6\\s_7\end{bmatrix} =
\begin{bmatrix}
1 & 0 & 0 &...
- 473
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 ...
- 131
0
votes
0
answers
38
views
Fully homomorphic encryption textbook suggestion
I am looking for mathematics textbooks which include a rigorous introduction to fully homomorphic encryption and especially CKKS / TFHE algorithms at the level of Boneh and Shoup's A Graduate Course ...
- 446
1
vote
0
answers
45
views
Conway Polynomial for p=2, n=3?
Im doing an exercise on Conway polynomials. As far as im concerned, for p=2, n=3 both
$f(x)=x^3 + x^2 + 1$
and
$g(x)=x^3 + x + 1$
satisfy every condition. According to every source i found, the latter ...
- 11
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 ...
- 11
0
votes
1
answer
37
views
Determine Whether a Pseudorandom Generator Is Secure
Let $G: \{0, 1\}^s \to \{ 0, 1\}^n$ be a secure pseudorandom number generator (with $s$ seed bits and $n$ output bits).
I have attached a problem below that I am confused about; Which generator $G'$ ...
user1329704
0
votes
0
answers
32
views
Problems about Probability Analysis of the Success Rate
I am currently reading a paper on linear cryptanalysis and I am a bit confused by the probability analysis of its success rate. I wonder if I can seek advice here?
Let $N$ be the number of given ...
1
vote
1
answer
101
views
distribution of square roots of unity $mod n$ | Factoring with inverse pair
I am writing a proof related to the RSA cryptosystem, specifically showing that given an inverse pair $d, c$ under multiplication mod $\phi(N)$, where
$$ dc \equiv 1 \pmod{\phi(N)}, $$
there exists a ...
- 83
1
vote
0
answers
29
views
Proof of Golomb's three randomness postulates for binary sequences [closed]
I want to prove that the binary sequence generated by a max-length linear feedback shift register (LFSR) satisfies Golomb's balance, run and autocorrelation postulates:
The numbers of zeros and ones ...
0
votes
0
answers
16
views
$\epsilon$-secure encryption system
Suppose the message space of a symmetric key encryption system is infinite (countable) with a probability distribution on it such that { $m \in M: Pr(m) \neq 0$ } is infinite. For a real number $\...
- 520
0
votes
1
answer
43
views
Confusion on the procedure of public-key and private-key cryptography
Procedure: $1):$ choose two distinct primes $p$ and $q$.
$2):$ calculate $n=pq.$
$3):$ compute $\phi(n)=T$.
$4):$ get $E$ from $gcd(E,T)=1.$
$5):$ get $D$ from $ED \equiv 1 \pmod{T}$
To encrypt the ...
- 1,541
4
votes
0
answers
128
views
Shortest vector problem as hidden subgroup problem
I posted this question on the cryptography stack exchange with a bounty, but I haven’t gotten much attention. I think part of the reason might be that I’m really interested in the use of group theory ...
- 2,980
1
vote
0
answers
20
views
Root finding of multivariate polynomials over the integers
TL;DR: is there any library for multivariate polynomial root finding over the integers?
I'm trying to implement an attack on RSA with known bits of p by using Coppersmith, such as shown in this paper. ...
- 11
-1
votes
2
answers
71
views
How do I solve a discrete log using pen paper for exam without bruteforcing it? [closed]
I have my Network Security finals. In elgamal cryptosystem, I am often encountering these equations like this
3 = (10^XA) mod 19
now everywhere I am finding only ...
- 111
0
votes
0
answers
15
views
Analyze the probability distribution of a specific sequence $S(x)$ with compensation mechanism
I'm developing a theoretical model for a sequence $S(x)$ equally spaced in the time dimension where each element is randomly preselected from set $\{1,2,...,L\}$, but the real selection(when it's turn)...
- 1
2
votes
1
answer
81
views
Embedding degree of an elliptic curve
I've been reading about the embedding degree of elliptic curves in Costello's "Pairings for Beginners". The following equivalent conditions are given for the embedding degree (p51):
where $...
- 291
2
votes
1
answer
145
views
Can we do any better bijective mapping of a permutation series which is only bijective for a probabilistic subset of its input domain?
So we want to bijectively map one path to another. But depending on start and target node we can only choose from a subset of all transitions. It would look like this:
We also do not know where one ...
- 77
1
vote
1
answer
81
views
RSA finding D key
Given the RSA public key find the decryption key d and decrypt the ciphertext c=5.
Known information:
n=221, p=17, q=13, e=11
$\phi(n) = (p-1)(q-1) = 16\times 12=192$
Equation for finding d:
$$ed\...
- 269
0
votes
2
answers
72
views
generating a polynomial algorithm from the given one-way function
I am trying to solve the following problem:
Suppose that $f : \mathbb{N} \rightarrow \mathbb{N} $ is a one-way function
and that for some function $l: \mathbb{N} \rightarrow \mathbb{N}$, the following ...
- 1,328
1
vote
0
answers
33
views
Confusion about Kraft-McMillan inequality for infinite alphabet
I was wondering if the Kraft-McMillan inequality continues to hold for codes with infinite alphabets. The reason I'm confused about this is because I was thinking about a code from $\{0,1\}^*$ to $\{0,...
- 59
1
vote
1
answer
84
views
Min and max value of index of coincidence
I am pretty new to cryptography and trying to understand some mathematical aspects. Studying different types of cipher, I came across the definition of index of coincidence which is as follows:
Index ...
- 11
2
votes
1
answer
67
views
Why do we get a connected 2-regular graph?
In reading "PUBLIC-KEY CRYPTOSYSTEM BASED ON ISOGENIES" by Rostovtsev and Stolbunov, they claim on page 8 that the set $U=\{E_i(\mathbb{F}_p)\}$ of elliptic curves with a specific prime $l$ ...
- 893
0
votes
0
answers
38
views
Why do 3 collinear points on an elliptic curve sum to $O$?
I'm working on a problem,
Let $\mathcal{E}:y^2=x^3-2x+1$ be an elliptic curve over the field $\mathbb{F}_5$, and let $P=(0,1)$ be among the points on $\mathcal{E}$. Find the equation of the line on ...
- 2,281
0
votes
0
answers
117
views
Confusion over the use of the term "module" in mathematics and post-quantum cryptography.
In post-quantum cryptography, there's a suite of algorithms based on "modular lattice". These schemes are defined in terms of vectors and matrices whose elements are polynomials of a fixed ...
- 211
0
votes
1
answer
49
views
Wouldn't it be easy to find private keys with the Diffie Hellman exchange? [closed]
I recently watched this video by Computerphile, where Mike explains the mathematics of the Diffie Hellman exchange. I've been wondering, since as explained $g$, $g^a$ and $g^b$ is public, can't you ...
- 21
0
votes
0
answers
74
views
the difference between a set and an ensemble
I am reading a paper in cryptography, there is something that I cannot understand well! here is the paragraph:
An inherently unobfuscatable function ensemble is an ensemble
$\{H_k\}_{k∈N}$ of ...
0
votes
0
answers
14
views
Notation for weighted norm of polynomial in lattice reduction
Where does this definition for the weighted norm of a polynomial $h(x,y)$ come from?
I do not understand the notation for the weighted norm of a polynomial because I am used to summation notation with ...
- 23
0
votes
0
answers
64
views
question about a derivation of an inequality [ related to wieners attack in cryptography ]
I had a question
regarding a formula derivation from a cryptography class
I am taking. Not really a crypto question.. Just more wondering how
does one go from LHS to RHS in above equality ?
$d<=(N^...
- 491
0
votes
1
answer
90
views
inverse problem about scalar multiplication on koblitz curves (or more exactly the secp256k1)
My problem is given $Q=nP$ to find point $P$ given 257 bits long integer $n$ and point $Q$.
It’s something possible on other curves but Koblitz curves have extra characteristic and can’t be converted ...
- 178
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.
...
- 105
1
vote
1
answer
71
views
Elliptic curves and zero-knowledge constructions are not shown over non-prime finite fields. Why?
What are the reasons that cryptography-related constructions -- such as featured in excellent explainers on elliptic curves on RareSkills and Practical Cryptography for Developers, and all the ...
- 538
0
votes
1
answer
53
views
What background is needed to understand lattices?
I'm trying to read the paper Finding a Small Root of a Bivariate Integer Equation; Factoring with High Bits Known but the subject matter is over my head.
I have an academic background in Applied ...
- 23
0
votes
2
answers
131
views
What does "a key is uniform" mean in cryptography?
In the lecture on Coursera platform, the inequality below was shown: there exists an algorithm $A$ such that
$$\underset{{k \overset{R}{\longleftarrow} \mathscr{K}}}{\operatorname{Pr}}\left[\left.A(G(...
- 29
0
votes
1
answer
120
views
What does $\mathbb{Z}_2^3$ mean? [closed]
What does $\mathbb{Z}_2^3$ mean? Is the subscript $2$ a modulo and the superscript $3$ dimensions of each element? I am studying lattice cryptography and set theory and I would like to know the how ...
0
votes
1
answer
58
views
Finding the period of the BBS sequence
Let $n=pq$, where $p,q$ are primes and $p \equiv q \equiv 3 \mod 4$. Choose an integer, $x_0$, such that $x_0$ and $n$ are co-primes. We define the sequence:
\begin{align}
x_i = x_0^{2^i} \mod n
\end{...
0
votes
0
answers
120
views
Unexpected Result from Finite Field Calculations in GF(2^8)
I'm performing calculations within the finite field $GF(2^8)$ and I can't seem to get the expected results. This is my first time working with finite fields, so my understanding is quite basic. I ...
1
vote
1
answer
30
views
Distinct derivations of polynomial over finite field
I am a student studying algebra and cryptography.
I wonder below question is possible.
Can I make some polynomials $f(x)$ over finite field that all derivations $f^{(k)}(x)$ are distinct when x is ...
- 13
0
votes
1
answer
71
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
51
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 ...
- 847
0
votes
0
answers
31
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&...
2
votes
0
answers
93
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
229
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
44
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
47
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
80
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
50
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
106
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
64
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
24
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
48
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