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)

2
votes
1answer
1k views

How to deal with negative exponents in modular arithmetic?

So I think I understand how to calculate something like $(208\cdot 2^{-1})\mod 421$ using extended euclidean algorithm. But how would you calculate something like $(208\cdot2^{-21})\mod 421$? Thanks,...
0
votes
1answer
46 views

Using an exponential cipher system, encipher the word HALT. where $p = 29, k = 11$, and $m = 1$.

Using an exponential cipher system, encipher the word HALT. where $p = 29, k = 11$, and $m = 1$. The progress I have made so far: H A L T $07, 00,11,19$ Since, $m =1$, we break this up into $2*m$ ...
0
votes
1answer
38 views

RSA Cryptography, finding the secret key

Alice, Bob and Eve are all present in the classroom. Alice and Bob want to agree on a password that Eve will not be able to know. Eve has access to all communication between Alice and Bob, and Alice ...
0
votes
0answers
35 views

Decrypting RSA message

I need help with a practice problem for an upcoming test. I've learned the answer to the problem is "well done", but don't know how to get there. Any help is greatly appreciated. Suppose that the RSA ...
0
votes
1answer
33 views

Find normal basis of the field $GF(3^6)$ and find the normal matrix

I am working with a homework is about normal basis on fields GF and I want opinions and maybe if you can help me in some doubts. 1) Find normal basis of the field $GF(3^6)$ which is understood as a ...
0
votes
1answer
12 views

Exhaustive search times: 2 to power k = 100 hours - double k, how many hours

An exhaustive search (i.e. checking all combinations of values) takes 100 hours to go through all permutations where a binary key has a length of k. $2^k$ = 100 hours where k is the number of digits ...
0
votes
1answer
19 views

Find a unique value for $d$ in $(d \cdot e) \pmod{F} \equiv 1$

Given that I know the value of $e$ and $F$. How to determine an unique integer value for $d$ in such a way that the reminder of the division of $(d \cdot e)$ per $F$ is equal to one? $(d \cdot e) \...
1
vote
1answer
28 views

Conditions for existence of quadratic residue congruent to 1

Under what conditions are we guaranteed an existence of quadratic residue 1 other than squares of 1 and -1. What conditions a number must satisfy to have such residue.
-1
votes
1answer
25 views

What is the bank need to get the message?

In Number theory $p=37, q= 43$, $\phi(pq)= 36 \cdot 42$, $e=5$ $d=?$ What does the bank need to get the message? I don't understand this problem. Can any one help me please?
0
votes
0answers
12 views

Security of $(k, 2k)$-bit generator for small seeds

Here is the problem I am working on for context. I have $\epsilon \le 1 - 2^{-k}$ and $\epsilon$ approaches 1 as $k \to \infty$ but I'm stuck on part c). The $f$ is secure iff there does not exist ...
1
vote
2answers
22 views

Connection between quadratic residue of a number to its factors'

Is it true that, If $N$ is product of two coprime numbers greater than 1. Quadratic residues of these numbers are quadratic residue of $N$ and vice versa? Can someone point me to a proof or show me if ...
2
votes
1answer
26 views

Invertible Uniform “PseudoRandom” Function

Perhaps this is better suited to a cryptography stack exchange, but I thought I'd try in mathematics in case this question is more obvious than I initially thought. I'm looking for a function $~f:\{1,...
0
votes
1answer
39 views

Hash functions - show how to find collisions

I'm currently trying to solve this exercise (sorry for image, it's for the notation and I'm not allowed yet to post images directly): I have read the exercise question a lot of times and I think I ...
1
vote
1answer
43 views

What is visual cryptography?

Question: 1. What is visual cryptography? 2. How does it work for secret image sharing? Attempt: I have tried to understand the concept of secret image sharing for black and white pixel from here ...
0
votes
1answer
23 views

To decrypt this version of Turing's code, does the decrypter actually need the secret key?

I am self studying MIT's Mathematics for Computer Scientists (link) There is a chapter in the readings on Number Theory, and it goes through the math involved in the cryptography methods used around ...
0
votes
2answers
15 views

ECB mode decryption

I have used the ECB mode (with block length $4$) to encrypt the message $m=1011000101001010$ into $c=0010011001001101$ using the key $$\pi = \begin{pmatrix}1&2&3&4\\2&3&4&1\...
1
vote
2answers
36 views

Calculating the discrete logarithm

I'm given a prime number $p = 1217$ I'm also given the following equations: $ 40 = \log2 \mod 64 $ $ 63 = \log3 \mod 64 $ $ 13 = \log5 \mod 64 $ $ 13 = \log2 \mod 19 $ $ 10 = \log3 \mod 19 $ $ ...
0
votes
1answer
27 views

Having trouble with understand the following derived equation by Euler Theorem..

We have the following equations $$\begin{align} d_p=&\ d\mod{(p-1)}\tag5 \\ d_q=&\ d\mod{(q-1)}\tag 6 \\ x_p=&\ y^{d_p}\mod p\tag 7 \\ x_q=&\ y^{d_q}\mod q\tag 8 \\ x=&\ ...
2
votes
1answer
27 views

Proof of $a^{m \, \pmod{\varphi(n)}} \equiv a^m\pmod n$

I am currently studying modular arithmetic for a course in cryptography. I have proved many operations, but I am stuck in one: Assume $n,a\in \mathbb{N}$ and $n\ge 2$. Prove that if $\gcd(a,n)=1$ ...
1
vote
1answer
29 views

Monoalphabetic Cipher

I am not sure how to get the key for the following Monoalphabetic Cipher question. This is a textbook question and I know the answer, but I juts dont know how they got the key. Question: ...
0
votes
1answer
22 views

Encryption - show probability for obtaining specific bit

Assume a person A encrypts a message which consist of the bits m1, ..., mn. The person is using the one-time pad algorithm. Another person B intercepts the ciphertext and we suppose he knows that mi (...
1
vote
0answers
22 views

Extended Golay codes are self dual

Show that extended Golay code $G_{24}$ and $G_{12}$ are self dual. To show it have to show that any two rows of $G_{12}$ and $G_{24}$ are orthogonal, that is inner product of any two rows are zero. ...
0
votes
0answers
4 views

In stinson's (2,n)-VCS How to calculate weight of rows of $S^1$ where all the binary n-vectors of weight $\lfloor{\frac {n}{2}}\rfloor$

Stinson introduced a new type of (2,n)-VCS. The $n\times m$ basis matrix $S^1$ is realized by considering all the binary n-vectors of weight $\lfloor{\frac {n}{2}}\rfloor$. Hence the pixel expansion ...
3
votes
1answer
186 views

One-time pad without preshared keys

It is my understanding that one-time pad encryption is the only unbreakable encryption, but suffers from the management of huge keys, and the secure distribution of those keys. Could one-time pads ...
1
vote
0answers
43 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
36 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
80 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 $n=...
0
votes
1answer
46 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
24 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
27 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
13 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
158 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
66 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
24 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
31 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
58 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 $\frac{r}{s}...
1
vote
2answers
75 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
30 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
708 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
44 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
30 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
29 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
31 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
33 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
43 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
26 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 $Pr(Y)=\sum_{e_k(x)=y}...