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)

0
votes
2answers
17 views

RSA Public key-Prove that if any one of p,q,ϕ(n) is known, then you can quickly use it to find the other two as well.

I'm a little confused as to how to go about this, I've read through the bottom answer to this question : RSA solving for $p$ and $q$ knowing $\phi(pq)$ and $n$ but in that question they find p and q ...
1
vote
1answer
1k views

How to determine the key-matrix of a Hill cipher where the encrypted-message-matrix is not invertible?

I am new to this subject and I have a homework problem based on Hill cipher, where encryption is done on di-graphs (a pair of alphabets and not on individuals). The alphabet domain is $\{A\dots ...
1
vote
0answers
17 views

Comparison of discrete logarithms.

Additive discrete logarithm: In $\Bbb Z_n^+$ we have to find $z$ in $zg=h\bmod n$ where $g$ generates $\Bbb Z_n^+$. $z$ is unique upto $z \bmod n$. Multiplicative discrete logarithm: In a cyclic ...
7
votes
1answer
1k views

How to reverse this bitwise AND-XOR encoding algorithm?

I have been given an "encoding" algorithm that does bitwise XOR and bitwise AND. Originally it's a C code that operates on integers with bit-shifts, but I have translated it into a simpler pseudocode ...
1
vote
1answer
33 views

RSA: Calculate $p$, having $n$, $e$ and half $q$

I need to calculate the $d$ private key in RSA. The data I know is $n$, $e$ and part of $q$. For calculating that d, I need to calculate $\phi = (p-1)(q-1)$, but, before I can calculate $\phi$ I need ...
1
vote
2answers
159 views

Isomorphic encryption or homomorphic encryption?

Many encryption functions are said to be homomorphic: http://en.wikipedia.org/wiki/Homomorphic_encryption As encryption functions are invertible, they can be considered one-to-one and onto on ...
7
votes
0answers
151 views

How to attack universal hash function based on finite-field arithmetic?

As per the Recursive n-gram hashing is pairwise independent, at best paper, I want to use the algorithm described in chapter 6 and 7 (page 7 - 10). The hash works as follows: Define a random ...
3
votes
1answer
31 views

Prove that for every polynomial $x^n$, $x^n(mod(x^4 + 1)) = x^{n(mod4)}$

I am trying to prove the following: Assuming $GF(2^k)[x]$ (where $k$ is a fixed natural number) is a ring of polynomials with coefficients in the field $GF(2^k)$. Prove that for every polynomial ...
0
votes
1answer
22 views

Using the Affine cipher, do we need $a^{-1}$ if we know gcd(a,26)=1?

I have just attempted the affine cipher with the word "code" $CODE = 02140304$ Lets choose our key as $(5,3)$, so our encryption is $y=5x+3$ $13211823=NVSX$ Now, to undo the code, I would have to ...
3
votes
1answer
29 views

Prove that if $X_2$ has a uniform distribution then $X_1 \oplus_2 X_2$ too

Assume we have two independent random variables $X_1$, $X_2$ with values in the set $Z_2 = {0,1}$. Prove that if $X_2$ has a uniform distribution then $X_1 \oplus_2 X_2$ has also the uniform ...
0
votes
1answer
26 views

Understanding simple equality [closed]

Looks like I got stucked. Could you please help me to understand that simple equality? If $A\in\mathbb{N}$ and $B\in\mathbb{N}$ than why do we have $$ (7^B \pmod{11})^A \pmod{11} = (7^A ...
0
votes
0answers
61 views

Finding an Elliptic Curve with 103 points

I am trying to solve the following problem: Find an elliptic curve over F101 with 103 points. I know all of the equations when needing to find alpha, and beta and all that when I am given two points ...
0
votes
1answer
18 views

Distances between identical strings in a long Vigenere

My queston is "Distances between identical strings in a long Vigenere ciphertext are 18, 30, 12, 12, 18. What is the likely key length"? I'm looking in the book and it has a similar problem that ...
1
vote
0answers
19 views

Pollard Rho - DLP Algorithm Implementation

I am working with Pollard Rho Algorithm DLP. I have developed in Java and Python the way to calculate the table to find the collisions, and then using congruences and some others tricks I am getting ...
0
votes
0answers
14 views

Show how to construct new AKE protocol

I'd appreciate if someone could help me with this exercise (image is for text and notation): http://i.imgur.com/S6xmkEX.png Could someone give me a hint, what am I supposed to do to show it?
0
votes
2answers
41 views

Finding modular inverse of every number mod 26?

I am looking at cryptography, and need to find the inverse of every possible number mod 26. Is there a fast way of this, or am i headed to the algorithm every time?
0
votes
0answers
12 views

generate unpredictable value with a shared key

I will start with an example. Some beacon like estimote Beacons use something called secure ID. The ID transmitted by the beacon change every 10 minutes autonomously without contacting the server. ...
0
votes
0answers
18 views

On discrete log calculation - safe primes need

Given a prime $r$ consider $g^z=h\bmod r$ where $z$ is unique mod $r-1$ where $r-1=2pq$ for primes $p,q$. Does this help simplify the discrete logarithm problem?
4
votes
1answer
104 views

Cryptosystem safer than RSA

As you know, the RSA system is based on the fact that factoring a number $n$ cannot be done in polynomial time ($P(\ln(n))$, not $P(n)$). The factoring problem is known to be in $NP$, but we don't ...
2
votes
0answers
22 views

One way functions and P = NP?

How can I show that no one way functions exist under assumption of P = NP?
-1
votes
3answers
67 views

How to calclulate 1/17 mod 60 [closed]

how can I calculate $ d = 17^{-1} (\text{mod} ~ 60) $ ? I was reading this article and then I wrote down this steps: 60 = 3 * 17 + 9 17 = 1 * 9 + 8 9 = 1 * 8 + 1 ...
0
votes
1answer
25 views

$p$ and $q$ 512-bit primes. What size in bits is $N=pq$?

$p$ and $q$ 512-bit primes. What size in bits is $N=pq$? I have that $p$ and $q$ are between $2^{512}-1$ and $2^{511}$, but cannot work out the rest. Thanks in advance.
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$? ...
0
votes
1answer
45 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
30 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
34 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
29 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
0answers
24 views

Algorithm to find password from hash value

I'm currently trying to solve this exercise (sorry for link to image, but there's a bit text): http://i.imgur.com/ETaCK0H.png But there's a few things in the exercise I don't understand. For ...
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 ...
2
votes
1answer
436 views

Calculating Probabilities for Substitution Ciphers using Frequency Analysis

I have been trying to put together a tool that can take in cipher text encrypted via a simple substitution cipher and calculate the most likely "key" (that is, how the plain text letters were mapped ...
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
25 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
21 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
25 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 ...
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
41 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
21 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 ...
-1
votes
0answers
30 views

Calculating block size for RSA

I am trying to encrypt some text via an RSA system, however I am having trouble working out how I decide what size the message blocks should be. p = 641 and q = 751 (n = pq) n = 481391 e = 347393 ...
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 = ...
1
vote
2answers
34 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
23 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
17 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
185 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
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?