Tagged Questions

Questions on cryptography and cryptanalysis, encryption and decryption, and the making and breaking of codes and ciphers.

learn more… | top users | synonyms

1
vote
0answers
10 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
22 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
0answers
59 views

The P versus NP and The Riemann Hypothesis [on hold]

This question is related to this article UPDATED which states Suppose that the Riemann Hypothesis is true such that For all $n>1$ and prime $p$ there exists a complex number ...
0
votes
1answer
22 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
51 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
26 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
28 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
22 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
28 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
votes
0answers
25 views

Algorithm and Complexity: Choosing a field [closed]

I need some help with following... I study maths with specialization in CS. I take the course "Algorithm and Complexity" and I have to choose one of the fields Computer Science (the operations of a ...
0
votes
0answers
13 views

calculating jacobi symbol (123456/111111111)?

I want to know how can I calculate jacobi symbol (123456/111111111) without using integer factorization? Thank you for your time in advance
0
votes
0answers
36 views

How do i find log 2 765 (mod 701) using index calculus method with base B = {2,3,7,11}? [on hold]

How do i find $\log_2 765 \mod 701$ using index calculus method with base $B = \{2,3,7,11\}$ ?
0
votes
0answers
9 views

Perfect secrecy not depending on probability distribution of message space

Say we have: $D$ - probability distribution on the messages space $M$. $M_1$ - a random variable of the messages under $D$. $C_1$ - a random variable of the encryption under $D$ (and some ...
1
vote
1answer
37 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
137 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
votes
0answers
107 views

To obtain prime factors without using prime factorization

(a) Let p; q and r be distinct odd primes. Suppose n = pq and m = pr. Given that you know that m and n share a common prime factor, but that you do not know the values of p; q;r, explain how you may ...
-1
votes
1answer
87 views

Suppose you are given p = 7 and q = 11 for an RSA scheme. Given a public key (e; n) = (13; 77), find the corresponding private key. [closed]

Suppose you are given p = 7 and q = 11 for an RSA scheme. Given a public key (e; n) = (13; 77), find the corresponding private key.
1
vote
1answer
24 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) = ...
1
vote
0answers
28 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
28 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$? ...
1
vote
1answer
32 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
35 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
21 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
0answers
23 views

Cracking RSA with the Same Public Key and Similar Plaintexts

I have two ciphertexts $A, B$ that were generated by the same public key $(N, 3)$ and where $m$ is the secret. We know that the plaintext of $A$ is $(37(m + 37))$ and the plaintext of $B$ is $(52(m + ...
0
votes
1answer
21 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 ...
0
votes
0answers
62 views

Rsa encryption/decryption (Updated)

1. Show that Bob can efficiently compute the encryption C(m) of the message m that he wants to send to Alice, knowing the public key but not the private key. Note: here (as well as in the rest of ...
0
votes
1answer
39 views

RSA and Crytography Research Paper

So I am starting a research paper on the topic of mathematics in Cryptography and RSA. I have little to no knowledge of this topic. I am trying to write an outline for my paper first. Are there any ...
1
vote
1answer
43 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
17 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
35 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
30 views

Are chaotic function one way?

Are chaotic functions also one way functions? Can they be used in cryptography?
0
votes
1answer
33 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
28 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
25 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
0answers
13 views

Computing the redundancy of language for a Vigenère cipher with m=5

Redundancy of L = 1- Entropy of L/ log base 2 {P} The Redundancy of L is given by 1 minus the Entropy of L divided by log base 2 of the Cardinality of the Plaintext space. Could someone advise me how ...
0
votes
1answer
15 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 ...
0
votes
0answers
25 views

Cardinality of the set $\mathbb{Z}_{26}^5$

I am trying to compute the unicity for a Vigenère cipher with $m=5$ to compute this I need the sizes(cardinality) of the plaintext space and key space they are the sets $\mathbb{Z}_{26}^5$. Integers ...
1
vote
1answer
47 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
12 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
27 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
32 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
33 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
35 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
33 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
43 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
66 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
23 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
324 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
17 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
28 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? ...