Skip to main content

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
2 answers
32 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 ...
Roman Maltsev's user avatar
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 ...
ephe's user avatar
  • 446
1 vote
0 answers
44 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 ...
Vanessa K's user avatar
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 ...
Yvonne's user avatar
  • 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'$ ...
user avatar
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 ...
35 honglang's user avatar
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 ...
FieldHouser's user avatar
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 ...
Kanan Mahammadli's user avatar
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 $\...
mshj's user avatar
  • 520
0 votes
1 answer
42 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 ...
Bowei Tang's user avatar
  • 1,435
4 votes
0 answers
127 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 ...
Joe's user avatar
  • 2,968
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. ...
Cnoob's user avatar
  • 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 ...
Pragyan's user avatar
  • 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)...
WxxW's user avatar
  • 1
2 votes
1 answer
77 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 $...
popstack's user avatar
  • 291
2 votes
1 answer
144 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 ...
J. Doe's user avatar
  • 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\...
Alix Blaine's user avatar
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 ...
SARTHAK GUPTA's user avatar
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,...
user675763's user avatar
1 vote
1 answer
80 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 ...
xterg's user avatar
  • 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$ ...
Shean's user avatar
  • 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 ...
mjc's user avatar
  • 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 ...
DannyNiu's user avatar
  • 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 ...
Henryk's user avatar
  • 21
0 votes
0 answers
73 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 ...
A.Ajorian's user avatar
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 ...
ender's user avatar
  • 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^...
Chris Bedford's user avatar
0 votes
1 answer
86 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 ...
user2284570's user avatar
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. ...
monopoly's user avatar
  • 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 ...
Jim's user avatar
  • 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 ...
ender's user avatar
  • 23
0 votes
2 answers
130 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(...
Iris's user avatar
  • 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 ...
smith33444's user avatar
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{...
Giorgos Mitropoulos's user avatar
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 ...
DurangoOlsen's user avatar
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 ...
hhhbbb's user avatar
  • 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 - ...
QuestionEverything's user avatar
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 ...
Jeffrey Rolland's user avatar
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&...
Severus' Constant's user avatar
2 votes
0 answers
92 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} \{\...
tuner007's user avatar
0 votes
1 answer
224 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 ...
Jacob V's user avatar
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 (...
maciek's user avatar
  • 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 = ...
jb1145's user avatar
  • 1
0 votes
1 answer
79 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$ ...
ZenithZero's user avatar
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 ...
ZhuJerry's user avatar
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 ...
Cotton Headed Ninnymuggins's user avatar
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, ...
Severus' Constant's user avatar
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$ ...
David Salgado's user avatar
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. ==== ...
Cooper Brian's user avatar
0 votes
1 answer
113 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: ...
Chris Bedford's user avatar

1
2 3 4 5
39