Questions tagged [cryptography]
Questions on the mathematics behind cryptography, cryptanalysis, encryption and decryption, and the making and breaking of codes and ciphers.
1,933 questions
1
vote
0
answers
41
views
Is there anything that would prevent peforming Weil Descent on binary curves of large characteristics?
The ghs attack involve creating an hyperlliptic curve cover for a given binary curve. The reason the attack fails most of the time is the resulting genus grows exponentially relative to the curve’s ...
- 206
-1
votes
0
answers
45
views
In finite fields of large characteristics,what does prevent shrinking the field size down to their larger order in order to solve discrete logarithms? [closed]
In the recent years, several algorithms were proposed to leverage elliptic curves for lowering the degree of a finite field and thus allow to solve discrete logarithm modulo their largest suborder/...
- 206
-1
votes
0
answers
16
views
entropy in substitution cryptography [closed]
this is a entropy question in cryptography . consider the substitution cipher code system in such way that the voiced characters (i,o,a,u,e) are assigned to themselves and silent characters are ...
- 1
-3
votes
0
answers
44
views
How many Primitive roots a number can have [closed]
How can we find number of primitive roots of a number is there any formula? Is there any shortcut method for finding primitive modulo
0
votes
0
answers
18
views
Understanding Canonical-embedding vs Coefficient-embedding in Ideal Lattices: Relation to NTT?
I'm trying to understand the relationship between different representations of ideal lattices, particularly the canonical embedding and coefficient embedding. While studying these concepts, I noticed ...
- 71
0
votes
0
answers
21
views
How to prove that the transition is made from statement (1) to statement(2)
Let $L$ be an $n$-dimensional lattice in $\mathbb{R}^n$ with basis $\mathbf{x}_1, \mathbf{x}_2, \ldots, \mathbf{x}_n$. Consider an arbitrary vector $\mathbf{z} \in L$ and write
$$ \mathbf{z} = a_1\...
- 1
-6
votes
2
answers
93
views
Why RSA uses exponentiation instead of multiplication by the inverse of $e^{-1}$? [duplicate]
I better clarify my question. If the problem of RSA is finding the inverse of $e^{-1} = e$ in:
$a^e \mod N$
Why don't we just do:
$ae \mod N$
for encryption, and
$ae^{-1} \mod N$
for decryption?
Since ...
- 5
1
vote
1
answer
54
views
Multiplicative Pairing functions
I'm looking into invertible pairing functions $P: \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N} $ that have some multiplicative properties in at least one argument.
The properties i'm looking ...
- 113
0
votes
0
answers
23
views
Looking for the name of this log-like method
In Elliptic Curve Cryptography you sometimes have to get from P to nP, say from P to 100P - the only allowed operations are adding of known quantities. So to get from P to 100P, we can of course just ...
- 292
0
votes
2
answers
79
views
Proof for affine ciphers being distinct.
For affine cipher, consider it over the set of $26$ english alphabets, let $V=\{a=0, b=1, c=2,\cdots, z=25\}.$ Let the multiplicative key be: $j,$ with $(j, 26)=1,$ i.e. $j \in \{1,3,5, 7, 9, 11, 15, ...
- 4,716
0
votes
0
answers
26
views
Question about a proof that an elliptic group generated using a singular curve with a self-intersection is isomorphic to an multiplicative group
I'm reading a proof on page 63 of this book:
I'm struggling on the simplification process that derives $(2.11)$, in which it substitutes $x_1, \ x_2, \ x_3, \ y_1, \ y_2$ into $$x_3= \left(\dfrac{y_2-...
0
votes
1
answer
66
views
Detect Duplicates in a Secret Santa
Imagine a Secret Santa with $n$ people. Due to a mix-up, there is a small chance that some people were assigned the same name. Is there any method by which the participants, without the help of a ...
1
vote
0
answers
39
views
In the book "Zero to Monero", what does Square Brackers around a parameter passed to a Hash function denote?
I am reading the Book "Zero to Monero", 2nd Edition, Section 3.1 Page 26:
Generate random number $\alpha \in_{R} \mathbb{Z}_{l}$, and compute, for all $i \in(1, \ldots, d), \alpha J_{i}$.
...
- 518
0
votes
0
answers
39
views
Solving a recurrence relation to show that the probability of double-spending decreases exponentially
The paper Analysis of Hashrate-Based Double Spending shows that the probability of a successful double-spending attack in blockchains based on proof of work decreases exponentially with the number of ...
- 1
1
vote
0
answers
48
views
The purpose of Enigma plugboard
It is well known the number of Enigma combinations with plugboard:
$${5!\over(5-3)!}\cdot26^3\cdot{26!\over(26-20)!\cdot2^{10}\cdot10!}=158,962,555,217,826,360,000$$.
So, $(26-20)!\cdot2^{10}\cdot10!$ ...
2
votes
3
answers
94
views
Proof of this derivative definition for polynomials in a finite field polynomial ring? $f(x)=q(x)(x-\alpha)^2+f'(\alpha)(x-\alpha)+\beta$
There is a protocol in a cryptographic paper that uses a definition for a polynomial derivative that I believe is right; but I can't use it until I am sure it is.
Can anybody give me a proper ...
- 450
1
vote
1
answer
49
views
Unconditional Security: How Does Quantum Cryptography Affect It?
I've been reading a paper ( "Unconditional Security in Classical
Cryptography" Petr Štika ) on cryptographic security, and I encountered some confusion about the concept of "...
- 209
1
vote
0
answers
49
views
Why is the extension field polynomial for AES irreducible but not primitive?
The AES standard (FIPS 197 page 8) states that multiplication over GF($2^8$) is done using the polynomial $m(x) = x^8 + x^4 + x^3 + x + 1$. This polynomial is irreducible. However, it is not a ...
3
votes
0
answers
241
views
Classification of an endomorphism ring of an elliptic curve over a finite field restricted to p-torsion points
Suppose p is a prime number, and not equal to c. c is the characteristic of a finite field. And an elliptic curve is defined over the finite field. Since an endomorphism of the elliptic curve ...
- 41
2
votes
0
answers
72
views
preimage attack and collision resistance of hashfunctions
I have some trouble understanding preimage resistance and collision resistance for hash functions. As definitions I use the once from wikipedia i.e.:
preimage resistance: for essentially all pre-...
- 23
0
votes
2
answers
61
views
How to study the cross-correlation distribution of the set of sequences consisting of both $m$-sequences and quadratic sequences?
Let $f(m):\mathbb{Z}^+ \rightarrow \mathbb{Z}^{+}_{even}$ is a function from the set of positive integer to the set positive even integer. Then by the $[f(m)-1]$-BCH code I mean the BCH code with ...
- 89
2
votes
1
answer
71
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 &...
- 919
1
vote
2
answers
79
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
1
vote
0
answers
51
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
35
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
45
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
34
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
112
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
45
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
40
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 $\...
- 540
0
votes
1
answer
49
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 ...
- 2,564
4
votes
0
answers
153
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,956
1
vote
0
answers
31
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
77
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
19
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
4
votes
2
answers
287
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 $...
- 393
2
votes
1
answer
154
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 ...
- 107
1
vote
1
answer
90
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\...
- 423
0
votes
2
answers
78
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,425
1
vote
0
answers
50
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,...
- 69
1
vote
1
answer
123
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
77
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$ ...
- 923
0
votes
0
answers
57
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,301
0
votes
0
answers
149
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 ...
- 231
0
votes
1
answer
55
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
136
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
19
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
67
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
125
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 ...
- 206
0
votes
1
answer
201
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.
...
- 141