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
1answer
17 views

$\tau_l(P,P)$ is a primitive $l$th root of unity

I'm trying to understand the Frey-Rück attack on elliptic curves, in particular the following lemma ($\tau_l$ being the Tate-Lichtenbaum pairing, $E(\mathbf{F_q})[l]$ the set of elements of $E(\mathbf{...
0
votes
0answers
8 views

Need help in Hashing to create a fingerprint

Given a pattern P of length m and a text T of length n (n >= m), in which all characters ...
2
votes
2answers
36 views

Choosing a Non-Confederate Volunteer

A magician is performing in front of a large crowd (around a 100 people, say) and wants a volunteer for a trick. The magician knows that he has no confederates in the crowd, but the crowd doesn't. How ...
0
votes
0answers
15 views

Find an example of a lattice such that LLL algorithm can't find the shortest vector of the lattice, satisfying…

I want to find an example of a basis of a lattice of dimension $n$ such that LLL algorithm can't find the shortest vector of the lattice, and such that the shortest vector of this lattice, say $b=...
0
votes
0answers
45 views

How to solve a modular inequality with optimization?

I have this: $x\le y$ $ y\lt m$ $x^2\mod m < y$ $y$ and $m$ are given. I am trying to maximize the value of $x$. Any advice on how to approach this?
0
votes
0answers
37 views

On Pohlig-Hellman prime power discrete logarithm algorithm

If $p,q$ are odd primes and suppose we know $x\bmod 2^rp^tq^u$ in $g^x=h\bmod q$ where $2^{r+1}p^{t+1}q^{u+1}|\phi(q)$ and $g$ generates $\Bbb Z_{n}^\times$ then what is the procedure and complexity ...
3
votes
1answer
37 views

Prove that $x^{n}\pmod {(x^{4}+1)}=x^{n \pmod 4}$

Assume $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 $x^n$ (where $n \in \mathbb{N}$) from $GF(2^...
0
votes
0answers
8 views

Why the light contrast of a set $\mathcal{E}$ of VCRG produced by an encryption scheme for a binary image B is defined as follows

In the paper "Image encryption by multiple random grids, Shyong Jian Shyu, 42(7):1582-1596 · July 2009" here, the light contrast of a set $\mathcal{E}$ of VCRG produced by an encryption scheme for a ...
0
votes
0answers
18 views

Brute force through the Diffie–Hellman key exchange

I was reading about Diffie–Hellman key exchange example on wikipeida: Alice and Bob agree to use a modulus $p = 23$ and base $g = 5$ (which is a primitive root modulo 23). Alice chooses a secret ...
0
votes
1answer
32 views

RSA cryptography

I saw on Wikipedia RSA algorithm and the private key has a condition imposed on it which says $$d \equiv e^{-1} \mod \phi(n)$$ where $n =(p-1)(q-1)$ but after a few steps $d$ condition becomes $$de \...
0
votes
0answers
32 views

If $n$ is divisible by a perfect square then $n$ is not a Carmichael number.

If $n$ is divisible by a perfect square then $n$ is not a Carmichael number. Going through the proof from Neal Koblitz's A Course in Number Theory and Cryptography...I am facing some difficulties to ...
0
votes
2answers
34 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
0answers
26 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 ...
1
vote
1answer
35 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 ...
3
votes
1answer
38 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 $x^n$...
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
37 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
27 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 \pmod{11}...
1
vote
0answers
76 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 ...
1
vote
0answers
26 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
44 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
16 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
22 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?
2
votes
0answers
24 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
90 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.
0
votes
1answer
32 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
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 ...
4
votes
1answer
105 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 ...
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
28 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 example,...
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
27 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,...
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
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 ...
0
votes
1answer
22 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
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
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
35 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 $ $ ...
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 (...