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

learn more… | top users | synonyms (2)

3
votes
0answers
78 views

Evaluate a rational function at infinity

In the context of the Tate pairing, I would like to know that it means to `evaluate' an $\mathbb{F}_{q^k}$-rational function at $\infty$. For instance, the reduced Tate pairing is $e_n:G_1\times ...
0
votes
1answer
118 views

Use Pohlig-Hellman to solve discrete log

We have $$7^x = 166 \pmod{433}$$ I need to find $x$ using the Pohlig-Hellman algorithm.
-1
votes
1answer
39 views

NTRU cryptosystem

For the NTRU cryptosystem (as described here http://en.wikipedia.org/wiki/NTRUEncrypt), why is it really easy for Eve to decrypt if $p$ divides $q$. My answer was that when Eve sees $e(x)= ...
1
vote
2answers
35 views

Undoing anonymous donations

All the students in a class are planning to do a trip. Not all of the students can afford it, and it is considered shameful to reveal their poverty. So it is suggested that anyone can donate ...
0
votes
1answer
29 views

How is it possible to write $\text {Pr} [M = m]$ where $M$ is random variable defined over a message space $\mathcal M$ and $m \in \mathcal M$.

In cryptography we consider random variables $K, M$ and $C$ over the key space $\mathcal K$ , message space $\mathcal M$ and cipher space $\mathcal C$, respectively. I've studied discrete mathematics ...
0
votes
1answer
48 views

NTRU cryptosystem

In the NTRU cryptosystem we are dealing with convolution polynomial rings and we compute $f(x)= T(d+1,d)$ and $g(x)= T(d,d)$ but when calculating their inverse in $R_q=(Z/qZ[x] / (x^N-1))$ and ...
1
vote
0answers
39 views

Find a polynomial of degree $8$ with integer coefficients with given root

algorithm to find a polynomial $f(x)$ s.t (1) $degree(f(x))<9$ (2) Integer coefficients (3) Absolute value of coefficients $< 10^5$ (4) f(39.770525) =~ 0 about to be <<10^-10 I ...
0
votes
1answer
26 views

Why in cryptography it is common to use the SAME key for all the group?

I believe that it is safer that each member should have his or her encryption and decryption keys that no one else knows. IN this case a message $m$ is sent as $m^{e_1}$ the receiver sends $t$ back as ...
0
votes
2answers
40 views

Continuous trapdoor functions?

Every trapdoor function I've seen has been a discrete function. Do there exist continuous trapdoor functions? If so, what's an example of a continuous trapdoor function? And if not, why not?
0
votes
1answer
48 views

Cryptography question

I think this is a pohlig hellman symmetric key system working in $\mathbb{Z}/p\mathbb{Z}$ Assuming Alice and Bob both have p (a prime) and k (a key) If Alice sends $m^k$ to Bob, can Bob raise $m^k$ ...
0
votes
0answers
33 views

Could this discrete logarithm problem be proved?

Given some values $X$, $Y$, $A$, $B$ and $p$, is there a way to show that there exists (or doesn't exist) an $n$ such that $X = A^n \mod{p}$ and $Y = B^n \mod{p}$? Alternatively, are there particular ...
1
vote
4answers
183 views

Elliptic curves (sum and multiply)

I was wondering if someone could give me some resources on elliptic curve cryptography. Specifically I need to know how to do something like: $y^2=x^3-x+1$ compute $(0,1)⊕(1,1)$ or $y^2=x^3+x^2-x$ ...
0
votes
0answers
41 views

Elliptic curve cryptography order

How do I compute an order a a point P on an elliptic curve? My question is specifically in reference to the attached photo. I understand how to do part a but I am totally lost in part b. I don't know ...
1
vote
1answer
28 views

Modular equation with non-integer numbers?

I was reading the book Homomorphic Encryption and Applications when I saw a modular equation involvind non-integer numbers. In short, on page 59 the book define the set $y$ as $\{y_1, y_2, .., ...
1
vote
1answer
31 views

Elliptic curves: Can I replace a coordinate with any modularly equivalent number?

I have a point (x, y) in an elliptic curve group. Suppose y is negative. Can I rewrite it as a positive number if that positive number is equivalent to y (modulo the characteristic of the group)? ...
0
votes
1answer
62 views

El Gamal encryption/decryption

First of all I want to ask if I did part a correctly? Alice has two secrets, $s_1 = 55$ and $s_2 = 108$ and wants to communicate one of them to Bob without knowing which one. Alice and Bob agree to ...
2
votes
1answer
71 views

Prove a residue matrix $A$ (with coefficients in $\mathbb Z_n)$ has an inverse if and only if $\gcd(\det A,n) = 1$

Prove a residue matrix $A$ (with coefficients in $\mathbb Z_n)$ has an inverse if and only if $\gcd(\det A,n) = 1$. I've always done matrix arithmetic in a field $\mathbb F$ and that is what ...
0
votes
1answer
27 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
99 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
126 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
66 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
125 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
33 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
39 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
33 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
33 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
60 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
143 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
28 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
131 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
335 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
69 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
44 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
32 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
33 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
49 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
43 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
57 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
51 views

Are chaotic function one way?

Are chaotic functions also one way functions? Can they be used in cryptography?
0
votes
1answer
49 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
31 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
25 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
90 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
56 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
40 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. ...