Questions on cryptography and cryptanalysis, encryption and decryption, and the making and breaking of codes and ciphers. Consider posting your question at Cryptography.SE.

learn more… | top users | synonyms (2)

1
vote
0answers
41 views

More efficient RSA using Chinese Remainder Theorem

Is there a way to increase the efficiency of the RSA algorithm by incorporating elements of the Chinese Remainder Theorem?
0
votes
0answers
34 views

Question about the following notation (groups and homomorphism)

So I was reading a paper on homomorphic encryption, and it in turn introduces some concepts that I didn't know much about before (primarily groups). I have a few questions but I'll first post the ...
1
vote
2answers
38 views

Proof of $[(a \; \text{mod} \; n)+(b \; \text{mod} \; n)] \equiv (a+b)\; \text{mod}\; n$

I'm currently self-studying a course in cryptography, and i understand the importance of understanding modular arithmetic fully. I have proved many operations on modular arithmetic, but one i am stuck ...
2
votes
2answers
72 views

RSA - Proof for dummies

I'm understanding the basic idea behind why RSA is secure, but I'm having a hard time understanding its proof with only basic knowledge of numbers theory. so I'm hoping that somebody can help me ...
0
votes
1answer
19 views

RSA cryptosystem decryption exponent

Show that in RSA cryptosystem the decryption exponent $d$ must satisfy the congruence $$de\equiv 1\pmod{{\rm lcm}{(p-1,q-1)}}$$ So in the RSA cryptosystem we pick two primes $p$ and $q$. Then ...
0
votes
1answer
32 views

Girth of directed graphs

The definition of girth of an undirected graph is defined as the length of the smallest cycle in the graph. Some directed graphs have no cycle (a directed path that stars and ends at the same vertex) ...
0
votes
0answers
23 views

I am currently working on the implementation of the Powerline System which is based on the Chor-Ri

I am currently working on the implementation of the 'Powerline System' which is based on the Chor-Rivest cryptosystem for my number theory project. There is a step in the key-generation phase of the ...
1
vote
0answers
23 views

Pocklington-Lehmer primality test

I have a question to the Pocklington-Lehmer criterion for primality testing which is commonly stated as follows: Let $n\in\mathbb{N}$ s.t. $n-1=a\cdot b$ where $a>\sqrt{n}$ and $a,b$ are coprime. ...
0
votes
0answers
12 views

how to impersonate A (Alice) in this protocol based on replaying a compromised session key. Is my answer correct?

Construct an attack based on replaying a compromised session key that allows an intruder to impersonate A. given protocol: ...
1
vote
2answers
147 views

Check if a number is Carmichael

I am trying to implement Modified Miller-Rabin Algorithm by Shyam Narayanan (https://math.mit.edu/research/highschool/primes/materials/2014/Narayanan.pdf). The algorithm demands to check if a number ...
1
vote
1answer
65 views

DLP in a Cyclic group

Let $q$ be a prime. $G$ is a cyclic group of order $q^2$. Show that for solving the DLP in $G$ it's enough to solve two distinct DLPs in two groups of order $q$. --- We are looking for an $x$ such ...
1
vote
1answer
23 views

Solving for the base of a modular exponent for El Gamal cryptosystem

We are given $B \equiv g^b \mod p$ and the values for $B,b,p$ but not $g$. How can we determine $g$ from the knowledge of $p, b$ and $B$, provided that $\gcd(b, p − 1) = 1$. The only solution that ...
4
votes
3answers
62 views

Using the fermat test to show 513 is not prime

I've been asked to use the fermat test for the base a=2 to show that 513 is not a prime number. Could someone please help explain what a base exactly is in this context? Thanks in advance!
0
votes
0answers
28 views

How can you distinguish modular exponentiation from random?

Let $N$ be the product of two primes and let $P$ be the smallest prime larger than $N$. Let the algorithm $R(N,s)$ return $s^{1/P} \pmod{N}$. Let the algorithm $\widehat{R}(N,s)$ pick a ...
1
vote
1answer
51 views

Dirichlet's 1842 Approximation theorem: Does this specific variant of the theorem actually exist?

From this pdf: Theorem (Dirichle,1842) Assume that $\gcd(a, b) = 1$. If $r,s$ are any natural numbers such that $\gcd(r,s) = 1$, and $|\frac{a}{b} − \frac{r}{s}| < \frac{1}{2s^2}$ then ...
1
vote
2answers
71 views

Proving Wiener's attack on RSA: help understanding what is meant by a “classic approximation relation”?

I am researching Wiener's attack on the RSA cryptosystem. The theorem, found here beginning on page 4, is as follows: Let $N=pq$ with $q < p < 2q$. Let $d < \frac{1}{3}N^\frac{1}{4}$. Given ...
0
votes
1answer
28 views

Trouble with substitution in modular arithmetic.

I was watching a video on the Diffie-Hellman key exchange, and they did: $$12 ^{15}\bmod \ 17 = 6 ^{13}\bmod \ 17$$ because $$3 ^{13}\bmod \ 17 = 12$$ So he substituted $3^{13}$ in for $12$. $$3 ...
1
vote
2answers
683 views

Extended Euclidean Algorithm in $GF(2^8)$?

I'm trying to understand how the S-boxes are produced in the AES algorithm. I know it starts by calculating the multiplicative inverse of each polynomial entry in $GF(2^8)$ using the extended ...
-1
votes
1answer
42 views

Cryptography using groups [closed]

For my math essay I decided to explore the use of group theory in cryptography; as opposed to looking at the coding algorithms I'd like to look more at the math behind it, assuming I know the basis of ...
1
vote
1answer
29 views

Substitution with modular arithmetic?

I was watching this video, and was curious how they were able to do the following: $$m^e\ modN = c$$ $$c^d\ modN = m$$ Therefore, $$m^{ed}modN = m$$ It's all simple algebra, but I wasn't sure how ...
0
votes
1answer
28 views

An RSA cipher has the public key pq=65 and e=7. What is the encrypted value of 3 integers a,b and c.

Question: An RSA cipher has the public key pq=65 and e=7. What is the encrypted value of 3 integers a,b and c. $$ \begin{align*} &M={ C }^{ d }mod\quad pq,\quad M\quad <\quad pq,\quad and\quad ...
0
votes
1answer
29 views

Encryption and Decryption with RSA Coding

I have been given $N=2021$ and $E=5$. I am to encrypt the the word 'he' where h is 18 and e is 15. Then I am to find D, and k, and decipher the encrypted message. My first question is whether i do h ...
1
vote
1answer
32 views

RSA Coding Question

I have been given that N=143 and the encoder E=7. An encrypted message 48 was received. I have to find the decoder and use it to compute the original message. This is how I did it but i'm not sure if ...
1
vote
0answers
24 views

Factoring of composite numbers of two primes

Let n=pq, with primes $p=x^a +1$ and $q=x^b+1$, for $x$, $a$, $b$ integers with $a$ not equal to $b$. Is $n$ hard to factor? If not what would be an algorithm and its complexity?
3
votes
1answer
40 views

Why is the discrete log problem intractable?

I have read the other questions on SE on this subject and they were not helpful to me, partially because I am not familiar with advanced mathematical notation. Let me explain the way I'm thinking of ...
0
votes
1answer
24 views

Perfect secrecy of affine cipher

How can I show that the affine cipher has perfect secrecy if the key $(k,a)$, where $k\in\{1,3,5,7,9,11,15,17,19,21,23,25\}$? I know to show perfect secrecy I need to show that ...
1
vote
4answers
47 views

Inverting Modular Exponentiation

How can I go about solving the equation $4 = y^4 \bmod{7}$? Do I have to try all of the possible $y$'s in between $1$ and $7-2$ or is there a smarter way that can be generalized for larger numbers?
0
votes
0answers
115 views

Markov Chain and cryptanalysis

Where I will be able to found papers to read the state-art of the use that Markov chain in cryptanalysis. I found this Canteaut, A. and Chabaud, F. (1998). A new algorithm for finding ...
0
votes
0answers
28 views

maximum number of homogeneous linearly independent equation over $\mathbb{F}_{2^m}$

In Field $\mathbb{F}_{256}$ we are given homogeneous equations in 255 variables from the field. It is said that maximum number of linearly independent such equations we can get are 247. Why ? To be ...
0
votes
0answers
32 views

How do I find the multiplicative inverse of a finite field polynomial using Euclidean Algorithm?

How would I use the Extended Euclidean Algorithm to find a multiplicative inverse of a polynomial in a Galois/Finite field...say, for example, $GF(2^3)$ ? Is it the same process as how it's ...
0
votes
1answer
73 views
3
votes
1answer
36 views

Explanation of this modular arithmetic example in “Understanding Cryptography”

Nothing is more frustrating than a book example that doesn't seem to make sense. I have been tasked to make an elliptical encryption accelerator, and it seemed prudent to read a book on cryptography, ...
1
vote
1answer
42 views

Solving $x^e =c$ in $\mathbb{F}_{p}$

Find all solutions to the equation $x^3=7$ in $\mathbb{F}_{13},\mathbb{F}_{19}$ and $\mathbb{F}_{35}$. In An Introduction to Mathematical Cryptography (Hoffstein et al), we have that proposition ...
0
votes
1answer
48 views

Digital Signature Algorithm (DSA) intuition and its relation to RSA

I already understands how to use the RSA algorithm to sign messages, as you can see in this post of mine. Searching about elliptic curves, I found a general algorithm called Digital Signing Algorithm. ...
2
votes
0answers
37 views

How Do Computers Factor Semi-Primes [closed]

How do computers factor large semi-primes? I know it's difficult but what process do they use? Is it simply a matter of dividing by all odd numbers under the square root of the semi-prime till they ...
0
votes
1answer
22 views

Special-purpose hash functions

I am trying to create a special purpose hash function that will have as few collisions as possible. $99\%$ of the input will be sequential numbers, from $1$ to $N$. The size of the hash table will be ...
29
votes
3answers
19k views

Why are very large prime numbers important in cryptography?

Firstly, you guys are awesome, and I learn quite a bit just from reading the questions of others. Secondly, a friend asked me recently why large primes are important for data security, and I was ...
0
votes
1answer
29 views

Proofs of congruence relations

Exercise 2.3 from "Introduction to Mathematical Cryptography" Let $p$ be a prime and $g$ an element in $\mathbb{F}_p^*$ of order $r$. (a) Suppose that $x = a$ and $x = b$ are both integer ...
0
votes
1answer
29 views

What are the values of b such that the matrix [(1,1)(b,1)] is invertible mod 26.

What are the values of b such that the matrix [(1,1)(b,1)] is invertible mod 26. I figured that the matrix is only invertible if its determinant and the n value 26 's gcd is 1, meaning they are ...
1
vote
1answer
353 views

Primitive Root Theorem

Let $p$ be a prime and let $q$ be a prime that divides $p − 1.$ (a) Let $a \in F_p$ and let $b = a^{\frac{p−1}{q}}$. Prove that either $b = 1$ or else $b$ has order $q.$ (Recall that the order of $b$ ...
1
vote
0answers
28 views

Find GCD of polynomials over GF(101)

Hello all I'm teaching myself cryptography, and I'm struggling with polynomial arithmetic over finite fields. I've some what been able to teach myself how to do the arithmetic over $GF(2)$, but when ...
0
votes
2answers
31 views

RSA Paper Example

I am reading the 1978 paper on RSA Algorithm. There is an example included in the paper and there is a section I can't get my head around. It says: Since $e = 10001$ in binary, the first block ($M ...
0
votes
0answers
22 views

Involutary Keys for Shift Cipher

Let $e_K(x)=(ax+k)\mod m$ and $d_K(x)=a^{-1}(x-k)\mod m$, where $K=(k,a)$ How can I show that $e_K(x)=d_K(x)$ if and only if $k^{-1}=k\mod m$ and $a(k+1)=0\mod m$?
0
votes
1answer
43 views

Proving if a permutation cipher is perfectly secret?

From what I've read, perfect secrecy in its most basic form, that the encrypted text reveals no information about the plaintext, be it structure or content. A permutation cipher is easy for me to ...
0
votes
1answer
35 views

Modular exponentiation and two primes

Given two primes $11$ and $5$, find all $\alpha> 1$ such that $$\alpha^{5} \equiv 1 \pmod{11}$$ What theorem will help me to find it out?
1
vote
1answer
65 views

The fastest Gröbner basis algorithm available?

for my undergraduate thesis I'm (pseudo) replicating algebraic attack on certain cryptosystem using gröbner basis approach. The heart of original attack was F5/2 algorithm (since the cryptosystem is ...
0
votes
1answer
27 views

Equation solution in modular arithmetic

Given two primes $11$ and $5$, find all $α > 1$ such that $α^{5} \equiv 1 \mod 11$. How would you compute that?
1
vote
1answer
54 views

Launching a Plaintext Attack against Affine Cipher

Update 2 Being new to the world of Stack Exchange I did not realize that there exists a site solely devoted to cryptography. In light of this, I hope someone could help me migrate this question to ...
4
votes
2answers
100 views

Who has revealed more about a secret password?

Today, Bob, a colleague of mine, accidentally revealed that his password contains a. Alice laughed, but then also inadvertently said her password does not contain ...
2
votes
1answer
18 views

Decrypting a message using rem()

Hello i have a problem in decrypting a message using this algorithm Beforehand : The sender and receiver agree on a large prime p, which may be made public. (This will be the modulus for all our ...