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

Generating a quadratic polynomial in RSA (cryptosystem)

Question: Suppose that n is the product of distinct primes p and q, so n=pq Show that p and q are the roots of the quadratic equation x^2 -(n+1 -φ(n))x + n Hence if n and φ(n) are known then n can ...
2
votes
2answers
102 views

Points on elliptic curve over finite field

Find the points on the elliptic curve $y^2 = x^3 + 2x + 2$ in $\mathbb F_{17}$. Do I have to guess a first point and then use an algorithm to spit out all other points?
0
votes
0answers
148 views

RSA and El Gamal Algorithms

I have to write a short report about RSA and El Gamal algorithms in cryptography. I just need to summarize them (how one would calculate the various components, what their strengths and weaknesses ...
0
votes
1answer
88 views

What is a probability ensemble?

The definition I have says An ensemble index by I is a sequences of random variables indexed by I. Namely, any X = {X_i}_{i \in I}, where each X_i is a random variable, is an ensemble indexed by I. ...
7
votes
1answer
130 views

Arithmetic background of this RNG code

I am trying to figure out the mathematical background of the random number generation of an old video game. It does iterations where it updates a 33-bit state consisting of the variables z (32-bit) ...
0
votes
1answer
27 views

Replacement Cipher

Replacement cipher: Let τ be a permutation of the alphabet, and apply τ to each letter of the message. Frequency analysis is useful for breaking this type of code. Decode the following, which was ...
0
votes
1answer
34 views

Encode WELCOME using RSA encryption

I am stuck on a problem using RSA encryption. We are encoding the message WELCOME. $W= 23$ $E= 5$ $L= 12$ $C= 3$ $O= 15$ $M= 13$ $E= 5$ $n =77$ $\text{and}$ $e =31$ I've come up with a couple that ...
2
votes
1answer
59 views

Breaking RSA if small subset invertible

I am trying to solve a problem which states that one can invert RSA if a small subset of the cipher text are invertible, the problem is as follows: Given a function which can invert the RSA ...
0
votes
1answer
43 views

Discrete Logarithm Problem with Base 2

Is there a special case for the discrete logarithm problem with a base of 2? For example, is it possible to solve for $a$ in the following problem without brute forcing $a$? (2^a) mod $p$ = $x$ ...
1
vote
1answer
35 views

Square and Multiply Decoding

Use the square and multiply method to decode the message 28717160 when $n=77$ and $d=13$. For the letter/number correspondence, use A=1. I have no idea what the "square and multiply method" is. I ...
1
vote
1answer
34 views

Proof of discrete logarithm?

If you have that $a$ is a primitive root mod p. How can you prove this discrete logarithm property? $log_{a}(b_1b_2) = log_{a}(b_1) + log_{a}(b_2)$ (mod $p-1$) I see the proof for the regular ...
0
votes
1answer
65 views

How to generate a simple RSA key to encrypt a very short message?

I'm trying to encrypt a message with RSA. I'd like to do this as part of a game/scavenger hunt I'm organizing for the holidays. I understand how RSA encryption works but I'm having trouble finding a ...
1
vote
1answer
55 views

Breaking RSA Ciphertext

Sam and Tim have set up their RSA keys $(e_s, n), (e_t, n),$ respectively, where the n-value is the same. Furthermore, it happens that $\gcd (e_s, e_t) = 1$. Suppose that their friend Rob wants to ...
1
vote
1answer
149 views

question about cryptography

Sam and Tim have set up their RSA keys (eS; n); (eT; n), respectively, where the n-value is the same. Furthermore, it happens that gcd(eS;eT) = 1. Suppose that their friend Rob wants to send both Sam ...
1
vote
1answer
29 views

Validity of ElGamal signature variation

I'm trying to solve excersise 7.6 from Hoffstein - Introduction to Mathematical Cryptography page 459 (hhttp://goo.gl/oRyInT) Let $p$ be a prime and let $i$ and $j$ be integers with $gcd(j, p − 1) = ...
2
votes
0answers
144 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
1answer
416 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
74 views

graduate level introduction to elliptic curve cryptography

I am looking for a good modern book / lecture-notes about elliptic curve cryptography. Does anyone have good recommendations?
2
votes
1answer
45 views

A Very Elementary Article or Webpage about Secret Sharing

I'm looking for an article or webpage about secret sharing with Latin squares, accessible to middle school students. I searched but found none. Can you help me? Thanks.
1
vote
0answers
34 views

Trouble Understanding Pinocchio (Verifiable Computing) Sparse Polynomials

I hope I'm asking the question properly. I've never asked anything on this exchange before, but I didn't know where else to ask. The paper in question I've almost got all the pieces to understand can ...
0
votes
1answer
34 views

Multiply point by scalar in elliptic curve group

I'm trying to understand how to multiply a point by a scalar to get a point in elliptic curve cryptography. Here's an example from my textbook. The group is E257(0, -4). That's shorthand for y2 = x3 ...
1
vote
1answer
50 views

Code that can be generated from 3 of 5 trusted people?

Suppose a computer contains sensitive data protected by a 3-digit passcode. (I understand this does not provide much security in the real world, but for the sake of the problem, assume only 3 digits.) ...
1
vote
0answers
45 views

Drawing a 5-stage binary LFSR with feedback Sm+5= Sm + Sm+1

Any guidance on how to draw this would be greatly appreciated I know this is more of a visual thing but I also want to go on to determine all the possible (different) cycles that are generated by this ...
0
votes
1answer
64 views

Proof related to RSA decryption

Can someone help me with this proof: Show that RSA decryption works for all messages a as long as the modulus m is a product of distinct primes. Thank you.
1
vote
1answer
67 views

Are chaotic function one way?

Are chaotic functions also one way functions? Can they be used in cryptography?
0
votes
1answer
51 views

Multiplication in the Galois field GF(3^3)

I am trying to compute $x^3$ in the Galois field $\text{GF}(3^3)$ using the irreducible polynomial $f(x) = x^3 + 2x^2 + 1$. From the expression $x^3 = f(x) + (2x^2 +1)$ I proceed to take the modulus ...
1
vote
1answer
33 views

Calculation of polynomial in the finite field

I'm trying to understand the McEliece cryptosystem and I'm looking to this paper http://www.mif.vu.lt/~skersys/vsd/crypto_on_codes/goppamceliece.pdf On page 26 they are calculating syndrome and ...
0
votes
1answer
37 views

RSA cipher Encryption with $n=210757$ and $a=3$ and Decryption with $n=14659$ and $a=3$

I think I understand correctly how to encrypt something with an RSA cipher, but I am a little lost on how to find the decryption key...(also I apologize for the formatting errors) An RSA cipher is ...
0
votes
1answer
26 views

Find $D$ in RSA cryptosystem

For the following encryption key $(n, E)$ in the RSA cryptosystem, compute $D$. $(n, E)= (451, 231)$ So I know $n=11*41$, so $m=400$. Now $D=$ inverse of $231 \ (mod \ 400)$. However I am not sure ...
1
vote
1answer
91 views

attack on RSA (factoring when knowing e and d)

This is the problem, I have to explain how works the algorithm on the image with modular arithmetic for a discrete math class., I tried to explain it, but I couldn´t. In the class, I have seen this ...
0
votes
0answers
15 views

Shamir sharing scheme - Calculating shares

In a (2, 5) Shamir secret sharing scheme with modulus 23, two of the shares are (1,22) and (4,8). Find the secret. $$S(1) = M + s = 22 (mod 23)$$ $$S(4) = M + 4s = 8 (mod 23)$$ Eliminate through ...
0
votes
1answer
77 views

finding the inverse of a matrx

In order to decrypt a cipher text using hill cipher, we must first find the inverse matrix of a given matrix. From this link http://en.wikipedia.org/wiki/Hill_cipher, ...
1
vote
1answer
43 views

Derivative of Diffie Hellman

Looking to get some clarification on this. We have the same three protagonists, Bob and Alice, trying to send each other a message. And Eve trying to figure out the message sent by Bob and Alice. ...
1
vote
1answer
36 views

Something similar to Euler's theorem

If $p$, $q$ are not equal primes. $n=pq$, $\varphi(n) = (p − 1)(q − 1)$, $d = \gcd(p − 1, q − 1)$. Is it true that for any $a$ such that $\gcd(a, n) = 1$ holds $a^{\frac{\varphi(n)}{d}} \equiv 1 ...
0
votes
1answer
57 views

Decryption of a RSA encrypted message is not working.

Using RSA with e=13 (encrypting power), d=17 (decrypting power) & n=33 (RSA modulus) I noticed that once I decrypted the encrypted message it would be different then the original message. Why is ...
3
votes
1answer
98 views

Toy cryptographic hash function for education purposes?

I'm teaching some high school students about number theory and cryptography, and I'd like a hash function (or ideally, a family of hash functions) that I can use as simple demonstration for ...
0
votes
1answer
188 views

RSA Algorithm Question [duplicate]

Suppose the primes p and q used in the RSA algorithm are consecutive primes (meaning they differ by 2). How would you factor n = pq? The ciphertext 10787770728 was encrypted using n = 10993522499 and ...
1
vote
1answer
70 views

Is there an error-correcting code where almost every word could be used as a codeword?

An error-correcting code for strings of length $n$ from a $K$ letter alphabet is a partition $\Pi$ of $K^n$ together with a choice function $\pi$ on $\Pi$. Let $A_i$ for $i<M$ enumerate $\Pi$, and ...
0
votes
1answer
42 views

Number of bits needed for Huffman code

Jake uses a Huffman code to compress i.i.d. (independent nad identically distributed) strings of symbols that come from a 5-ary alphabet ($A$, $B$, $E$, $R$, $S$) where the probabilities of occurrence ...
-1
votes
2answers
334 views

Distribution of the RSA numbers

Let's take a random prime $p$. For the sake of the argument let's say $\log(p)\approx 1000$. Let's suppose all numbers between $p$ and $p+1000^2$ are composites. What is the approximate probability ...
0
votes
0answers
26 views

Two-dimensional affine cipher

Problem: We have a two-dimensional affine cipher with $n = 2,\,\,\,\mathcal{P} = \mathcal{C} = {\mathbb{F}_{16}^2}$, where $\mathcal{K} = \{ A,\,\,b\} $ and $b = (0,0)$. The encryption and decryption ...
0
votes
1answer
90 views

Decrypting a Vigenere cipher with affine key

Consider a cipher where the method of encryption is to perform a Vigenere cipher on a plaintext, with the key word being an affine cipher of the letters a,b,c,...,z. How strong would this cipher be? ...
1
vote
2answers
25 views

reducing exponent in modular arithmetic

Im struggling with an example excercise because I have problemes to comprehend an step in the calculation $3^{36} \mod 59 = 3^{7} \mod 59$ How can I reduce the exponent $36$ to $7$? I tried it with ...
1
vote
1answer
73 views

Does Zhang's result on primes makes RSA weaker?

I read from Finnish newspaper ( http://www.uusisuomi.fi/tiede-ja-ymparisto/72212-matemaattinen-ongelma-eli-2-300-vuotta-mies-subway-tiskin-takaa-ratkaisi#.VBwhYp09F2k.facebook ) the article of Zhang's ...
1
vote
0answers
81 views

Finding a point on an elliptic curve

I have an elliptic curve with the equation $ y^2 = x^3 + ax + b $ in modulo p, where p is prime. I also have a point G on that curve. How can I find another point that isn't a multiple of G? I ...
0
votes
1answer
40 views

Cryptography probability

62% of plaintext messages have even parity. 56% of odd plaintext messages have ciphertext with even parity. 48% of even plaintext messages have ciphertext with even parity. What is the probability ...
2
votes
1answer
40 views

The modular n-th root (mod p*q)

I am interested in the solution of the following modular equation. Is the solution unique? If not, how difficult do find more than one solutions? $$x^n \equiv a \; \bmod (p\cdot q)$$ where $p$ and ...
0
votes
1answer
30 views

Affine cipher and shift cipher

I have the following question: An affine cipher with key $K(0,b)$ is equivalent to a shift cipher explain why I don't think this is true, and assume it is a typo, $K(1,b)$ I would agree, since ...
1
vote
0answers
46 views

The number of Balanced Boolean functions

Suppose we have n-variable Boolean function (BF) and we know that the weight of a Balanced BF is $2^{n-1}$. The total number of BFs are $2^{2^n}$, Affine BFs are $2^{n+1}$ and Linear BFs are $2^n$. In ...
0
votes
1answer
28 views

Cayley table for 2-bit integers ${Z_4}$

Let us consider the multiplication operation, denoted by $ \odot $ on the set of 2-bit integers ${Z_4}$ defined as follows: $$\eqalign{ & a \odot b = (ab\,\bmod \,5)\,\bmod \,4\,if\,a \ne 0,\,b ...