Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [cryptography]

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

2
votes
1answer
26 views

Extended Euclidean Algorithm yielding incorrect modular inverse

In order to solve an ElGamal cryptographic problem, I need to solve 8x≡1 (mod 17) Or simply, find the inverse of 8 in the context of modular 17. By the Extended ...
2
votes
1answer
64 views

Elliptic curve addition: why does it work in any field?

Supposing I have an elliptic curve E(K): y^2 = x^3 + Ax + B with char(K) != 2,3, why do the formulas for EC addition work in any field. The formulas make sense in ℝ, for example we calculate the slope ...
0
votes
1answer
34 views

The indicator of a Boolean function

In the paper "Componentwise APNness, Walsh uniformity of APN functions and cyclic difference sets" by Claude Carlet, it is written that: Let F be any power function on $F_{2^n}$ and $\Delta _{F}=\{F(x)...
0
votes
0answers
14 views

Example of univariate Boolean function

So, I've been working a bit with Boolean functions and I've stumbeld uppon a hurdle. I know that every Boolean function $f:F_{2^n}\to F_2$ can be represented using ANF, and that I've understood. The ...
0
votes
0answers
34 views

Is it possible for $a = 2$ mod $17$ to be a Fermat non witness for $n = 85$?

Let $n = 85$. Suppose that an element $a \in (\mathbb{Z}_n)^*$ satisfi es the relation $a = 2$ mod $17$. Is it possible for such $a$ to be a Fermat non witness for $n = 85$? So a Fermat non witness ...
1
vote
1answer
24 views

Understanding affine cypher / Euclidean math

$$e(x) = (ax + b)$$ $$d(y) = a^{-1}(y-b)$$ I need to prove that $$e(x)=d(y)$$ iff $$(a^2)=1$$ and $$b(a+1)=0,$$ so I tried working with $d(ex)$ to show they can be equivalent: $$ax + b = a^{-1}(ax + ...
0
votes
0answers
27 views

How to figure out one of the keys in an affine cipher?

I have been told that one of the keys in an affine cipher is 33. The Mod is 37 - the set being the alphabet + numbers + space. So the affine function is $ax + b$ $(mod$ $37)$ with $a$ and $b$ ...
-2
votes
1answer
53 views

Number Theory - Modular Arithmetic [duplicate]

How would you do this problem? The equation $x^2 \equiv 1 \bmod 493$ has two obvious solutions: $x \equiv \pm1 \bmod 493$. Using that $x \equiv 86 \bmod 493$ is another solution to find a ...
0
votes
0answers
27 views

How can a node establish pairwise shared key with other nodes using its own polynomial share together with other's public values?

A server has a symmetric bivariate polynomial $ F(x, y) = \sum_{{i,j}=0}^{t-1}a_{i,j}x^iy^j$ $\in GF(p)[X, Y] $ of degree $t-1$. For simpliciy, $ F(x, y) = a_{0,0}+a_{1,0} x+a_{0,1}y+ a_{1,1}xy$ mod ...
1
vote
0answers
32 views

Is Elliptic Curve Discrete Logarithm Problem NP-Hard or NP-Complete

I have trouble classifying Elliptic Curve Discrete Logarithm Problem as NP-Hard or NP-Complete. Where does ECDLP belong? Any brief comprehensive answer is encouraged. Thanks.
1
vote
1answer
31 views

Understand a factor base method to compute discrete logarithms

I am going through my cryptography notes in a section about sub exponential factor base methods for computing discrete logarithms, and I come across a statement I don't understand about an algorithm ...
2
votes
0answers
76 views

What is the description of a group?

I am currently reading a paper on verifiable delay functions and when talking about the security of Pietrzak's succinct argument the description of a group is mentioned: Let $\operatorname{GGen}(\...
0
votes
0answers
36 views

Pohlig-Hellman Algoithm , finding x for $g^x=a$ in $F_p$, where $g$,$a$, and $p$ are given [duplicate]

I'm new to cryptography, I've just learned the Pohlig-Hellman Algorithm, but I'm having some difficulty understanding where a particular step. In $g^x=a$ in $F_p$, where $p=433$, $g=7$ and $a=166$. I ...
0
votes
1answer
41 views

discrete logarithm and calculating with modulo

I have the following scenario: Let $p' = 3, q' = 5, p = 7, q = 11, n=pq = 77$. Then $\mathbb{Z}_{77}^* = \{a \in \mathbb{N} \ \big\vert\ 1\leq a \leq 77, gcd(a, 77) = 1\}$. Furthermore $QR_{77} = \...
2
votes
1answer
49 views

Factorization of large (60-digit) number

For my cryptography course, in context of RSA encryption, I was given a number $$N=189620700613125325959116839007395234454467716598457179234021$$ To calculate a private exponent in the encryption ...
-1
votes
1answer
56 views

Find all pairs of positive integers $(x, y)$ for which $261x + 48y = 7881$ [closed]

How do you use the Euclidean Algorithm to solve the following: Find all pairs of positive integers $(x, y)$ for which $261x + 48y = 7881$
1
vote
0answers
42 views

Irreducible Polynomial of Galois field

We know that one irreducible polynomial on $Z2[x]$ is $x^8 + x^4 + x^3 + x + 1$. How to check that it is irreducible? And how to generate irreducible polynomial for any degree?
0
votes
5answers
54 views

Solve for $x, \;23+35 x ≡ 4$ (mod $ 13)$

I can simplify the equation, but I get stuck at the last step: $\;x≡ 9^{−1} (4-10)$ (mod $13$). My issue is that I am unsure how to compute this by hand.
0
votes
1answer
18 views

Show the affine cipher $e(m)=am$ fixes at least two messages in $\mathcal M=\mathbb Z/N\mathbb Z$

Let $N$ be an even integer. Consider the affine cipher on the space of plaintext messages $\mathcal M=\mathbb Z/N\mathbb Z$ with encryption function $e(m)=am$ where $a\;\epsilon\; \mathbb Z/N\mathbb Z$...
2
votes
1answer
44 views

RSA Cryptography and grouping integers

I know that for RSA cryptography, you need a public key which is a semi-prime $n$. I am trying to do a question involving the key $n=187=11 \times 17$ (I know in reality one would use a much, much ...
1
vote
2answers
27 views

Decrypting an Affine Cipher $ e(m)=am+b\pmod{27}$ knowing $e(8)\equiv 14$ and $e(26)\equiv 5$

I began by setting up a system of linear equations: $$14\equiv 8a+b \pmod{27}$$ $$5\equiv 26a+b\pmod{27}$$ and then subtracted them to get: $9\equiv 9a \pmod{27}$. I know $9$ doesn't have a ...
0
votes
1answer
17 views

Translating binary plaintext into alphabetic plaintext using an $18$-digit base-$26$ integer system

I'm working on a cryptography problem and went through the long process of decrypting a sent message to get a $27$ digit number. It then says: Plaintext blocks have $18$ letters and that such an ...
0
votes
1answer
24 views

Show that an Affine Cipher with a prime modulo $N$ fixes exactly one plaintext message $m$ in $\mathcal M$

Let $N$ be a positive integer. Consider the affine cipher on the space of plaintext messages $\mathcal M=\mathbb Z/N\mathbb Z$ with encryption function $e(m)=am+b$ where $a,b\;\epsilon\; \mathbb Z/N\...
1
vote
2answers
55 views

Cryptology Proof

Given prime $p, 0 < m < p$ and $ed \equiv 1 \pmod{p-1}$, prove $ m^{ed} \equiv m \pmod{p}$. I get that this is hinting at a proof very similar to that of RSA, and that I have to consider when $...
0
votes
1answer
66 views

Are there solutions to $x^2 = 171\pmod{203}$?

The question is: Give any two solutions $x^2 = 171\pmod{203}$. I am pretty sure this is no solution but I am not sure. How would I go about writing a proof to show there are no solutions for my ...
1
vote
3answers
60 views

Square Root Mod

On my homework it says $\sqrt{48}\pmod{73}$ but I have in my notes that $\sqrt{y\pmod{p}}\equiv y^{(p+1)/4}\mod{p}$. Which I feel like I should use. When I type it as it appears on the homework into ...
0
votes
4answers
66 views

Can you please solve $7^{-1} \mod 480$ using extended Euclidean Algorithm?. Kindly show the steps till end

I am solving RSA algorithm wherein I have to find d by finding $7$ inverse modulo $480$. Please help in solving till end using extended euclidean algorithm Using extended Euclidean Algorithm for ...
2
votes
1answer
58 views

RSA - Under What Circumstances does Encryption Key Also Decrypt Cyphertext?

I used primes $p = 7$, $q = 13$, to get $n = 91$ and $\phi(n) = 72$. I chose $E=19<\phi(n)$, but found that $D=19$, which meant $x^E=x$ $(mod$ $n)$, i.e. the encryption is just the identity ...
0
votes
1answer
51 views

Number of points needed to determine a sparse univariate polynomial over a large prime field with known support

Consider a sparse polynomial $f \in \mathbb{F}_p[x]$, of maximum degree $k$, with a known support of $t$ terms. That is, we know a set $I \subseteq \mathbb{N}$ such that $\#I = t$ and $f(x) = \sum_{i \...
0
votes
0answers
18 views

How to obtain private key of Elliptic curve by factorization?

Okay i am trying to understand how the elliptic curve cryptography can be cracked by using factorization. Am not getting any clues after searching the internet can someone show me how your help will ...
0
votes
0answers
19 views

differential uniformity solution of exponential box

BelT cipher uses a Pseudo-exponential substitution box. The $\lambda$ and z values selected for the the BelT gives a differential uniformity of 8. \begin{equation} exp_\lambda,_z (x) = \begin{...
-1
votes
1answer
111 views

Miller-Rabin Primality Test-Witnesses and Liars - Implementing in Python

I have been studying the Miller-Rabin Primality Test, and am interested in implementing a code in Python to count witnesses and liars. In the basic code to determine if a number is probably prime or ...
2
votes
1answer
60 views

RSA Group theory proof

Let $q,p$ prime numbers and $n=pq$. Let $r$ random from $Z^{*}_n$ and $e$ random element which is not contained in $\varphi(n)$. all values except $p$ and $q$ are known. Let $f_1(m) = m^e \text{ ...
0
votes
1answer
71 views

Solve for $b$ in the equation $2^b \equiv 893 \pmod{1373}$

The question asks to solve for $b$ in the following equation: $2^b \equiv 893 \pmod{1373}$ However I am not sure how to solve this, as I only know how to solve for integers on the left hand side. The ...
0
votes
2answers
32 views

Affine cypher. Find function and plaintext

I was checking the following Affine Cipher / modular aritmethic exercise: You intercept a ciphertext YFWD, which was ciphered using an affine cipher. You know ...
0
votes
0answers
13 views

How to do the shortcut function in ECC when N (Private Key) is Known

When N or private key is known, we don't have to iterate through all the process just to get the final location given the two initial points. How is that shortcut function implemented given the ...
0
votes
1answer
29 views

Can modulize a multiplication of some numbers

Let's suppose we have this function: $f(n)= a^n b^{n-1} c^{n-2} \mod p$, where $a,b,c,p \in Z^*$ and $p$ is also a prime. I want to create software in C, Java, etc., that calculates the function ...
1
vote
1answer
53 views

Cryptography RSA system

I everyone, I am considering an RSA encryption over the multiplicative group $G = (Z/nZ)$ of the ring $Z/nZ$, where $n = pq$, and $p$ and $q$ are distinct odd primes. I assume that $H=\{x^4|x\in G\}...
0
votes
0answers
18 views

Logic swap issue

User A encrypts data [X] as RdL}s)g*ush_GzE User B encrypts data [Y] as XgU4abG@XH$%k}yH User A sends RdL}s)g*ush_GzE to User B User B sends XgU4abG@XH$%k}yH to User A How can User A ...
1
vote
1answer
37 views

Solving non coprime coefficient equation

Suppose I have an equation $24\times a \equiv 12 \pmod {26}$. How do you solve this type of equation when the coefficient is not coprime with $26$?
0
votes
0answers
41 views

Zero knowledge proof

I have the following problem Let $p$ be an odd prime. For $g\in \mathbb{F}_p^{\times}$ and $y\in \mathbb{F}_p^{\times}$ we define $$DL_p=\{(p,g,y) \space \vert \space \exists x\in\mathbb{Z}/(p-1)\...
0
votes
0answers
12 views

Gröbner basis vs Brute Force Attacks on GF(2) polynomial system of equations?

I'm studying cryptography and I have a question regarding the complexity analysis of algorithms. In AES cryptography, the Gröbner basis algorithm for solving systems of polynomial equations over the ...
2
votes
2answers
44 views

Find the elements of the extension field using primitive polynomial over $GF(4)$

Let $p(z) = z^2 + z + 2$ be a primitive polynomial. I want to construct the elements of the extensional field $GF(4^2)= GF(16).$ Since $p(z)$ is primitive polynomial , it should generate the ...
0
votes
0answers
65 views

inverse of a binary matrix modulo 2

All operation are modulo 2. I want to calculate the inverse of a matrix. Is there any easy way to do that? I have tried the usual method of finding determinant and all that.
6
votes
1answer
47 views

Verifying if a given polynomial is primitive polynomial

Given a polynomial: $f(x) = x^2 + 2x + 2$ over $GF(3)$. I want to know if i can use it to construct $GF(3^2)$. My approach: This equation satisfies first condition: A primitive polynomial is ...
1
vote
0answers
30 views

Understand an algorithm to find a prime of bit length $k$

My cryptography notes gives this algorithm for finding a prime of bit-length larger than or equal to $k$. Determine an optimal bound on the set of small primes to be sieved $(2,3,...,p_t)$ and let $M=...
0
votes
1answer
27 views

Understanding an excerpt of notes on RSA using the Chinese Remainder theorem

I have a description in my cryptography notes of a way to make RSA more efficient using the Chinese Remainder Theorem. Let $p,q$ be large primes, $N=pq$ , $e$ be the public encryption exponent, $d$ ...
-3
votes
1answer
34 views

Can anyone decipher this RSA encryption? [closed]

The given public key is (1602467, 829) and the message is: 618010.854516.292790.447129
0
votes
1answer
27 views

Creating the generator matrix of the linear block-code

How can i create a generator matrix for $(5,3)$ Linear block-code over $GF(2^2)$. Most of the books mention the operations on this matrix and also that the choice of the basis vector is not unique ...
2
votes
0answers
61 views

2 sequences defined as (really untrivial) limits

I've been working for a while on these 2 sequences, which arose in cryptography : $$\forall b\geq2,$$ $$\delta_b = \lim\limits_{p\in\mathbb{N}\to\infty}\left[\sum_{n=0}^{\infty}\left(1-b^{-p}\right)^{...