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

learn more… | top users | synonyms (2)

2
votes
0answers
24 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
0answers
36 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.
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
29 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
117 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 ...
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)? ...
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
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
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?
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 ...
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
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 ...
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
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
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 ...
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
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
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
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
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
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) = ...
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 ...
0
votes
0answers
25 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
22 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
65 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
46 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
21 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 ...