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
2answers
5k views

RSA: Fast factorization of N if d and e are know

I stumbled across this paragraph in a paper: Hence, user b cannot decrypt C directly. But using e and d , user b can quickly factor N. How is it possible to speedup the prime factorization ...
0
votes
4answers
10k views

Calculator model with mod function?

I'm wondering does anyone know of a scientific calculator with a mod function? In C# this is shown as follows (just in case there are any other mods that a mathematical non-savant such as myself ...
1
vote
1answer
2k 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 Z\}...
1
vote
1answer
27 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=...
-1
votes
0answers
25 views

Problems using number theory and groups in Cryptography [closed]

I am writing a research paper in maths, and have experience with undergraduate level number theory and group theory. I read about applications of these concepts in cryptography which look really ...
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 ...
2
votes
1answer
365 views

Does there exist some relations between Cryptography and Algebraic Topology? [closed]

We know that there are many application of Cryptography in our real life. Are there any relation between Cryptography and Algebraic Topology? If yes, please suggest me some link or books. Thanks ...
2
votes
1answer
439 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 ...
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 ...
7
votes
0answers
167 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 ...
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
31 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 ...
1
vote
3answers
210 views

Fermat Factorization

Does anyone know how I can use Fermat Factorization to find the two prime factors of the integer $n = pq = 321179$? I am not sure how to go about solving this and any help would be much appreciated!
3
votes
1answer
68 views

What is a good book on Cryptography with an emphasis on algebraic aspects?

I have heard of the subject "Cryptography" but never looked much into it. But this summer, I thought is the best time to look into the subject and see if it will interest me. In U.G, I did ...
4
votes
1answer
83 views

RSA-keys are not good?

PK := (n, e) = (1765937, 23755) SK := (n, d) = (1765937, 1734043) Can someone tell me, given these keys, what is not good about them, meaning it should not be very difficult to break it? (Except ...
0
votes
1answer
27 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
178 views

How to show a function is negligible?

Let $neg(x)$ be a negligible function (see here for the definition). Let p be a polynomial function such that $p(k)\geq 0$ for all $k>0$. What can we say about $f = neg(p(k))$? Is $f$ a ...
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 ...
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
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 ...
1
vote
2answers
174 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 ...
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 ...
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
25 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
43 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
15 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?
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 ...
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
88 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$? 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
31 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
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?