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.

1
vote
1answer
49 views

$p, q$ are prime, $(p - 1) \bmod q = 0$, $(q^7 - 1) \bmod p = 0$ and $q$ is known, how to get $p$

$p, q$ are primes (which is very big and can't be brute-forced), $$(p - 1) \bmod q = 0$$ and $$(q^7 - 1) \bmod p = 0$$ $q$ is given, is there any way to calculate $p$ without brute-forcing? Also, ...
0
votes
0answers
8 views

Properties of Gaussian Distributions on lattice

I have some troubles when I read a paper of Micciancio and Regev - "Worst case to average case based on Gaussian Measures". In the proof of lemma 4.1 (in picture): Authors had called $Y$ be the ...
1
vote
0answers
5 views

The derivation of mathematical model used to quantify the non-randomness of difference distribution table (DDT)

It is mentioned in Reverse-Engineering the S-Box of Streebog, Kuznyechik and STRIBOBr1, a mathematical equation to quantify the probability that all coefficients in the DDT of a random 8-bit ...
0
votes
0answers
19 views

References for cryptography on elliptic curves? [duplicate]

What are good books to learn cryptography on elliptic curves? I'd like a mathematician oriented book. Thanks.
0
votes
1answer
15 views

Calculate a Primitive Polynomial LFSR

I tried to search on the internet, to read my course multiple times, but the only thing I see are definitions of the primitive polynomials for an LFSR. I have an exercise: Find the primitive ...
0
votes
1answer
34 views

Given that $n = 1279033001$ is a product $n = pq$ of distinct primes $p$ and $q$ and that $175205^2 ≡ 1$(mod n), factorise $n$.

I have tried using Fermats factorisation and Pollard $p-$method but unfortunately I'm running into rounding errors with my calculator. I'm not sure how $175205^2 ≡ 1$(mod n) is helpful
0
votes
0answers
43 views

Embedding a polynomial ring into $\mathbb{Z}_{n^s}$

My setting is the following: $n$ is a product of two big primes (RSA-like), and I am given a $R = \mathbb{Z}/n^s\mathbb{Z}$ as a space to work with. I would like to represent elements of $R$ as ...
0
votes
0answers
18 views

How to generate a (secure) elliptic curve of composite order?

How to generate a (secure) elliptic curve of order $k$ ($k$ is not be a prime)? Elliptic curves with prime order can be generated via different approaches. I wonder how to generate an elliptic curve ...
0
votes
0answers
17 views

Generator of set

For the cryptographic scheme I need to generate the following parameter: g is a generator of Q (Q is the set of quadratic residues modulo N (N = pq is the RSA modulus) How to calculate g? What ...
1
vote
0answers
13 views

How to use Logarithm in the Sieving step of Quadratic Sieve technique

I am working on a program to factor large semi-prime numbers. I am using the simple Quadratic Sieve technique. My program works well but lot slower because during the sieving process (when I was ...
0
votes
1answer
25 views

How is scalar multiplication performed on a point in Elliptic Curve Cryptography

can someone please explain how the multiplication(386(0,376)) is performed in the given example in the image. ECC example
0
votes
1answer
41 views

Elliptic Curve Division Points

There is a statement about the number of division points, which I've read in a few papers, but it never seems to have any references where it comes from or why it is true. The statement is the ...
2
votes
1answer
44 views

Is $X^{E} \equiv X \;(\text{mod}\; n)$ a potential problem in the RSA cryptosystem?

This is Exercises 11 from Section 7.3 of the book "Abstract Algebra: Theory and Applications" (aata-20180801) by Thomas W. Judson. Find integers $n$, $E$, $X$ such that $$ X^{E} \equiv X \;(\text{...
2
votes
1answer
36 views

RSA - Quadratic Sieve - Relation Building - How to choose $b$ in $F(b)$?

On p153 of Hoffstein Pipher & Silverman's book "Intro. to Mathematical Cryptography", the list of numbers: $$F(a),F(a+1),F(a+2),...,F(b)$$ is stated. Where $N$ is number to be factored, $F(T)=...
1
vote
3answers
44 views

Prove that $G$ has at most one element of order $2$

Suppose G is a cyclic group generated by $g\ \epsilon\ G$, i.e. $G=\{e,g,g^2,...,g^{n-1}\}$ where $n$ is the order of $g$. It can be shown that if $0\le k\le n-1$, then the order of $g^k$ is $\frac{n}{...
0
votes
0answers
19 views

How to construct cyclic and self dual code (12,4)

Question is: Construct cyclic and self dual code (12,4). Both codes has 4 bits for data and 12 bits for codeword. Construct generation matrix for both codes. Prove that both codes are equal. I am ...
0
votes
0answers
13 views

Why can multiparty Schnorr signatures not be solved for linearly?

If you only need the notation skim down to the bold line. Quoting from en.bitcoin.it Schnorr signatures are a proposed future extension that give a new way to generate signatures r, s on a hash h....
1
vote
1answer
19 views

Clarification on the order of an element in the Pohlig-Hellman algorithm for groups whose order is a prime power

According to wikipedia: Why does $h_k=(g^{-x_k}h)^{p^{e-1-k}}$ have an order that divides p. Shouldn't the order divide $p^{k+1}$?
1
vote
0answers
24 views

Reducing exponent in modular arithmetic (Distributed ElGamal decryption)

I'm currently trying to make an ElGamal system decrypt in a distributed fashion, so as to never reveal the secret key in play. To that effect, the secret key is put into a polynomial as the constant ...
1
vote
0answers
44 views

Division by Mersenne primes

Mersenne primes are used in Computer Science and Cryptography because they support fast modulo computation. If $p$ is a Mersenne prime, $n \bmod p$ can be computed with just a few add and shift ...
1
vote
1answer
37 views

Assuming that it was enciphered with a generalized Caesar Cipher with multiplier r and shift constant s, find r and s and decipher the message.

Message to decipher: ZWSTO BPJOG BYQIP JOUWO OZGVS MPJOS MPQAI We are just leaning Caesar Ciphering in class and im kinda confused. I know that to do this we need the equation C is congruent to rP + ...
0
votes
0answers
23 views

CRT- finding the value of number from it's tuple representation.

In Chinese Remainder Theorem(CRT): If $A\ \ \mathcal{E}\ Z_m$, and $a_i = A mod\ m_i$, where, $$ M = \prod^k_{i=1} \ m_i $$, and $m_i$ are pairwise relatively prime. Now, if M is great, it(is said ...
0
votes
1answer
47 views

Product of generalised Reed-Solomon Codes

I know the definition of a generalised Reed-Solomon Code: $$ GRS_{n,k} (\alpha, v) = \{(v_0 f(\alpha_0), ..., v_{n-1}f(\alpha_{n-1}) ): deg f < k \}.$$ I know also that the product of two GRS ...
1
vote
1answer
42 views

Modulo of modulo. Let $p,N$ be positive integers with $N$ divides $p$. Does for every integer $X$, $[X\pmod{N}]\pmod{p}=X\pmod{p}$?

Let $p,N$ be positive integers with $N$ divides $p$. Does for every integer $X$, $[X\pmod{N}]\pmod{p}=X\pmod{p}$? This question is similar to [1] - I consider it different due to $N$ now dividing $p$ ...
0
votes
0answers
20 views

Bit length of a quotient q

I'm trying to compute the bit length of q in a situation: Let a be k-bit and b be l-bit where a$\geq$b then by division algorithm we can write a=bq+r with 0 $\leq$ r$<$b What I've done so far: ...
2
votes
3answers
45 views

How can I increase the complexity of a number and maintain uniqueness

I have an 8-digit number and you have an 8-digit number - I want to see if our numbers are the same without either of us passing the other our actual number. Hashing the numbers is the obvious ...
2
votes
1answer
59 views

RSA - statements re $\phi(n)$, $\lambda(n)$ and $n$, given $n$,$|n|=1024bits$, and $e=65537$

Assume $n=pq$, with $p,q$ primes, $e=65537$, and length of $n$, $|n|=N=1024$ bits = 309 decimal digits. $p,q$ are unknown. I am trying to understand the information sourced from Wikipedia page on RSA ...
1
vote
3answers
47 views

Divisor on Elliptic Curve

A divisor on an elliptic curve E is a formal sum of points $$D=\sum_{P\in E}n_P(P)$$ where the $n_P$ are integers only a finite number of which are nonzero. Could anyone please explain what is the ...
1
vote
2answers
21 views

In galois field- how does modular arithmetic

The following is given in the text that I have: In $GF(2^8)$ [Galois Field] let: $$h(x)=x^8+x^4+x^3+x+1$$ $$x^8 \bmod h(x)= [h(x)-x^8]$$ I basically don't understand the second step I think $h(x) mod ...
0
votes
1answer
43 views

Factoring $9788111$ via Gaussian elimination over $\mathbb F_2$

I am trying to follow page 142 to page 144 of An Introduction to Mathematical Cryptography by Hoffstein, Pipher & Silverman, where they give an example using Gaussian elimination over $\mathbb F_2$...
0
votes
3answers
105 views

What are examples of a 10 digit safe prime number?

I am stuck with a question with regards to finding an example of 10 digit safe prime number. I need the number for cryptography purposes. (for Diffie-Hellman key exchange) I know that a safe prime is ...
1
vote
2answers
43 views

How do I properly do back substitution and put equations into the form of Bezout's theorem after using the Euclidean Algorithm?

For some problems, even longer ones, I've been able to see the pattern and properly do back substitution to bring a series of equations I've derived using the Euclidean algorithm to the form of Bezout'...
0
votes
0answers
13 views

ElGamal Hash Function

The ElGamal signature scheme presented is weak to a type of attack known as existential forgery. Here is the basic existential forgery attack. Choose $u,v$ such that $\gcd(v, p — 1) = 1$. Compute $r = ...
0
votes
1answer
50 views

How to figure out a 615 digits long decryption key given these RSA properties?

I have a public key $(n,e)$ where modulus $n$ has 615 decimal digits. a decryption exponent $d$ with 8 decimal digits currupted with known positions. a plaintext-ciphertext pair $c_1 = m_1^e \bmod n$...
0
votes
1answer
34 views

motivation for encryption algorithms

I'd like to address this question to encryption algorithms in general, but, just for the moment taking DES for instance. When studying the DES algorithm, we're shown the structure and how the ...
0
votes
0answers
19 views

Is it possible to find $x$, knowing the following: $((z_1s_2 - z_2s_1) (v_1 s_1 - v_2 s_2))^{p-2} (\text{mod } p)$

This puzzled me over the last weekend, before everything let me say it's quite possible that the equation doesn't have a "solution" but it is a special case that follows from a solution. In any case, ...
0
votes
0answers
33 views

Algebra using sage

Can anyone help in writing a code to find the list of idempotent and primitive elements of a group algebra, the examples goes like this. Let $p$ be an odd prime such that $\bar2$ generates $U(\mathbf{...
1
vote
0answers
47 views

Understanding cryptography

Basically, I am trying to study cryptography, and the primary resource that I have is: Introduction to Cryptography by D. R. Stinson, So, I barely made pass the SPN algorithm described and am ...
-1
votes
3answers
68 views

Index Calculus with factor base {2,3} to solve $ 3^x \equiv 11 \pmod{37}$ [closed]

I'm not sure how to start this, I know I'm supposed to use log to help me out..But my textbook isn't very clear
0
votes
0answers
18 views

Show that weight of code is equal to the minimal number of rows in the control matrix

Show that weight of code is equal to the minimal number of rows in the control matrix. My solution: Let $a$ is vector, $C^{*}$ is control matrix, $w(a)$ - weight of code. We want to show $a*C^{*} = ...
0
votes
1answer
32 views

Common modulus attack question RSA.

If we are in the context of understanding how Common Modulus Attack for RSA: $C_1=M^{e_1} \pmod{n} $ $C_2=M^{e_2} \pmod n $ We know that if $\gcd(e_1,e_2)=1$ the attack works fine. ¿What would ...
3
votes
2answers
69 views

Discrete Log solve using Index-Calculus producing incorrect 'r' value.

I have a discrete log that I need to solve to aid in a Cryptography problem, that deals with both programming and mathematics, so I was unsure where to post this problem, feel free to move me if ...
2
votes
1answer
31 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
82 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
37 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
15 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
36 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
39 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$ ...
0
votes
0answers
33 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 ...