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
0answers
10 views

Effect of seeds on the generation of keystream from a LFSR

I have a question regarding something I noticed about LFSR seeds. I tried different seeds in a simple LFSR with polynomial of “x4+x+1”, most cases I got equal amount of 1s and 0s in the keystream ...
0
votes
5answers
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 ...
0
votes
0answers
40 views

dining metaphysicians

I thought I'd read about this problem years ago, but cannot find the answer online. There is a more well-known dining philosophers problem that is vaguely similar. https://en.wikipedia.org/wiki/...
0
votes
1answer
28 views

Diffie Hellman Problem

I know that in Diffie Hellman, the final key (from Bob's point of view the final key is calculated as follows) KB = (gx mod n)y mod n, where x represents Alice's private no. y represents Bob's ...
2
votes
1answer
446 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 ...
2
votes
0answers
368 views

Suggest solutions book

Does somebody know solutions manual for book "An Introduction to Mathematical Cryptography" by Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman?
2
votes
0answers
28 views

Is a possible use of a Mill's constant the encapsulation/encryption of messages?

I wonder if the way that Mill's constant is defined could provide a good data encapsulation and encryption method if instead of encapsulating primes, for instance a simple ASCII message is ...
3
votes
1answer
167 views

Proof of an alternative form of Fermat-Euler's theorem.

I want to know a proof of an alternative form of Fermat-Euler's theorem $$a^{\phi (n) +1} \equiv a \pmod n$$ when $a$ and $n$ are not relatively prime. I searched some number theory books and a ...
1
vote
0answers
37 views

How to provide Mathematical Proof for number theory scheme?

I have a set S={1,2,...,N-1}. N=pq (where p and q are RSA prime numbers). Scenario is that User need to retrieve the Database blocks without revealing his block index to the Server i.e, Private ...
1
vote
0answers
26 views

How good is the pseudo-radom-sequence assuming the truth of RH?

The Riemann hypothesis is equivalent to the claim that the sequence of moebius-values (numbers not being squarefree are skipped) behave similar to a random walk. Let's assume that the Riemann ...
0
votes
0answers
19 views

Discrete Logarithm vs Integer Factorization

Can anyone please tell me if finding discrete logarithm is considered more difficult than integer factorization? We have very advanced methods to find factors of large composite numbers like Number ...
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 ...
2
votes
2answers
5k views

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

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 ...
1
vote
1answer
19 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{...
2
votes
2answers
42 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
9 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 ...
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
0answers
48 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
41 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
380 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 ...
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
173 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
19 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
34 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
35 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
211 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
71 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
31 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
27 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
37 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
185 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
79 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
27 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
47 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
18 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
23 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
26 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
108 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.