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

learn more… | top users | synonyms (2)

0
votes
1answer
46 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.
3
votes
0answers
32 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
24 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
29 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
17 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
38 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
37 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
21 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
31 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
38 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
30 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
118 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
26 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
0answers
24 views

Advice needed in Cryptography

I'm currently in my undergrad studies (3rd Year in 2015) , majoring in pure mathematics and statistics. I'm thinking of pursuing cryptography for my Honours project, as its the closest thing that ...
-3
votes
1answer
325 views

Formula for $N=xy$, where $N$ is given and $x$ & $y$ are both unknown prime numbers.

Can any body can give me a formula for all composite prime numbers. $$ N=xy$$ where $N$ is given and $x,y$ are both unknown prime numbers. Ex. ...
1
vote
1answer
27 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
26 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)? ...
7
votes
1answer
103 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
21 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 ...
0
votes
0answers
25 views

Algorithm for solving 2PLE

I have a trouble with this article which trats an attack on the Isonorphism Problem with 2 linear secrets. At the end of page 11 the author analizes the properties of a system using a certain ...
2
votes
1answer
47 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
19 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
1answer
56 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?
-2
votes
3answers
44 views

Help me solve 6^141 (mod 4189) for my exam preparation [closed]

I wanna ask you a difficult question (*for me). how do you solve this question? calculate 6^141(mod 4189) thank you
1
vote
0answers
21 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
18 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. ...
0
votes
0answers
15 views

RSA and El Gamal

I was wondering if anyone knew where I could find some examples of encryption with El Gamal and RSA using very large primes? I wrote a code for El Gamal and RSA but I want to test it with some known ...
0
votes
1answer
334 views

Why does RSA have to use Euler's Totient function?

$$\begin{aligned}m^{ed} &\equiv m\bmod n\\ ed &\equiv 1 \bmod \phi(n)\\ \end{aligned}$$ Why does the modulus of the modular multiplicative inverse have to be the totient function? Won't any ...
2
votes
1answer
53 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
27 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

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
24 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 ...
0
votes
1answer
29 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
29 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
2answers
1k views

How to work RSA encryption/decryption

I need an array populated with characters and integer keys for each, and I want to, using this set, encode messages, and then decode them later on . Essentially I am trying to write RSA algorithm for ...
0
votes
1answer
38 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
25 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 ...
1
vote
1answer
25 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) = ...
0
votes
1answer
30 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 ...
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
3
votes
1answer
68 views

Notation: “belongs to” with an R subscript

I've run into an expression: $x_i \in_R \mathbb{Z}_q$ – and I wonder what this means. An example paper is here, here's example in Wikipedia. Can anybody help me? Thanks in advance.
0
votes
0answers
12 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
140 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
41 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
votes
1answer
98 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
0answers
47 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
38 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
34 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
36 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
22 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 ...