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

learn more… | top users | synonyms

3
votes
1answer
42 views

Is it possible to find plaintext from ciphertext if (n) and (a) are known?

I have a couple of questions pertaining to a RSA problem. I need to decipher some ciphertext and find out what the original plaintext was. n = 2537 and a (or the exponent) = 11. Encrypting function: ...
0
votes
1answer
12 views

How to determine the key-matrix of a Hill cipher where the encrypted-message-matrix is not invertible?

I am new to this subject and I have a homework problem based on Hill cipher, where encryption is done on di-graphs (a pair of alphabets and not on individuals). The alphabet domain is $\{A\dots ...
0
votes
0answers
19 views

What is rational point on elliptic curve over Galois field

It is clear what is a rational point on elliptic curve, when the curve is defined over real numbers. But if it is defined over Galois field, what is a rational point? If necessary, supply an example, ...
1
vote
1answer
12 views

Exponention cipher - prove unique mapping from plain text to cipher text

At the heart of RSA, is the exponention cipher: C=M^e mod P (where C=ciphertext, M=Plaintext e=exponent and P=modulus.) How do you prove that two different plaintexts don't map to same ciphertext?
2
votes
2answers
49 views

Irreversible Math Function

Is there any function which will take two inputs, (a+b) as one input and c as another, and return a result from which c can only be computed only if a and/or b are known individually? Basically I ...
2
votes
1answer
573 views

Solving Diffie–Hellman problem for low primitive root

What's a good way of solving the Diffie–Hellman problem when those exchanging the message have chosen a low primitive root $g$ (e.g. $g=3$)? Of course you could brute force it but I'm interested in ...
1
vote
2answers
83 views

Elliptic Curve Crypto

I had just read a primer about ECC, I see how it can be complicated. Something I haven't been able to determine is what information does the client machine get to help decrypt the data? The whole ...
2
votes
3answers
38 views

Is 6 a generator of this Group?

I've had the opportunity to learn about the mathematics behind Diffie-Hellman key exchanges, prime numbers, generators of groups, and all that good stuff. I wish I understood it, it's discomforting ...
1
vote
1answer
342 views

Affine cipher - Modular multiplicative inverse

I want to decrypt an Affine cypher. Definition: a^-1(c-b) a = 5, b = 13 Range: Alphabet (26 letters) Letter to decrypt: K (c = 10) So: = 5^-1(10-13) = 5^-1(-3) I am not sure what do to next. ...
1
vote
1answer
351 views

question on how to decrypt the message

A message is encrypted using an affine cryptosystem in which plaintext uses the 26 letters A through Z (all blanks are omitted), the letters are identified with the residue classes of integers (mod ...
1
vote
0answers
36 views

Find f(x,y) = 1 if(x=y) else 0 (f must only do addition/substraction multiplication or division)

This maybe more of a computer science problem but maybe the solution lies in number theory. Given integers x,y, find F(x,y) = 1 if x=y else F(x,y) = 0 The obvious solution Negate( x-y ) cannot be ...
0
votes
2answers
41 views

Median primes and cryptography

I've been considering something involving median numbers. If an integer is directly in the middle of two integers, is it possible to accurately extrapolate what two it is between? Can a prime be in ...
1
vote
2answers
113 views

RSA - finding $p$ and $q$

If the public key $(e,n)$ and the private key $(d,n)$ are known, how can I find the $p$ and $q$ primes by the easiest way? When $n$ and $\varphi(n)$ are given was easy to solve, but this issue I can't ...
2
votes
2answers
47 views

Find the $4$ sq. roots of $100$ in $ U_{209}$. Identify which square root of $100$ is square.

Find the $4$ sq. roots of $100$ in $U_{209}$. Identify which square root of $100$ is square. (Not the $4^{th}$ root, but the $4$ square roots). I honestly don't even know what this question is ...
3
votes
1answer
102 views

If the same message is sent to Alice and Bob who are using different public keys, how can somoene following the channel find $m$

Alice and Bob are using different public keys, Alice is using ($N_{1,2}$) and Bob ($N_{2,2}$). A message, $m$ is sent to both of them using their RSA systems. It is also true that $N_1$ and $N_2$ are ...
1
vote
2answers
56 views

Factor $n=59305397$ given that $ p-q \le 10 $

So what is given is that $n=pq\ ; \ p-q = \sqrt{(p+q)^2 -4n}$ Rearranging the $p-q$ equation, I get $$ p+q = \sqrt{(p-q)^2 +4n}$$ So, $$2p = (p+q) + (p-q) \ \text{and} \ q=\cfrac{n}{p}$$ However ...
4
votes
2answers
314 views

RSA encryption. Breaking 2048 keys with index

I have some thoughts on this. First, I want to say I am no expert on cryptography, I just know some stuff, and I took a cryptography class in University. I am very interested in this topic. I ...
4
votes
0answers
69 views

Are large prime numbers kept secret? [duplicate]

I've read several times that modern cryptography is based on the fact that multiplying two primes is easy, whereas getting the prime factorization of a random big integer is very hard. (see here) ...
4
votes
1answer
112 views

Lenstra's Elliptic Curve Algorithm

I am currently trying to understand Lenstra's Elliptic Curve Algorithm for factoring integers. As a source I use "Rational Points on Elliptic Curves" by Joseph H. Silverman and John Tate. They ...
0
votes
1answer
76 views

How to find primitive point on an elliptic curve?

Reading about Elliptic curve cryptography, i came across primitive point's or generator point's but found nothing on how to generate such points any help would be appriciated.
1
vote
1answer
54 views

PowerMod: Solving for the base

Given the problem $c^d \mod n = m$ and values for $d$, $n$, and $m$, how would one solve for $c$? A general solution or approach would be fine, as well as the values for my specific problem are as ...
0
votes
0answers
22 views

Permutation certification. A cryptographic hash function for permutations?

Alice has a secret permutation $\alpha$ (a random permutation of an $n$-set; $n=18$ would be a decent choice for the application I have in mind). She wants to convince Bob that she has $\alpha$, but ...
1
vote
1answer
23 views

Cryptology - Compare the amount of work the cryptanalyst is likely to require - Single vs. Double rotation

"Suppose a cryptanalyst suspects that SECEC SYHRI IRFET SSETE INLST AFNIA FSOAI HFSRT TEATE was obtained by a succession of two rotations with different block lengths and rotation amounts. Compare ...
1
vote
0answers
23 views

What is the algebraic normal form of $F(x,y,z)= Trace (\alpha x^{24}) + x^{312} + yz$?

Let $w$ be a primitive element of $\mathbb F_{5^4}$. Let $\alpha=w^{13}$. Define, $F:\mathbb F_{5^4}\times \mathbb F_{5}\times \mathbb F_{5} \Rightarrow \mathbb F_{5} $ as, $$F(x,y,z)= Tr (\alpha ...
4
votes
1answer
70 views

Permutations: If I know $\alpha$ and the cycle structure of $\alpha\beta$, can I find $\gamma$ for which $\gamma\beta$ also has this cycle structure?

Suppose we have two permutations $\alpha$ and $\beta$ (of a set $S$ of size $|S|=n$), and I know $\alpha$ and the cycle structure of $\alpha\beta$. But I don't know $\beta$. Can I find a ...
1
vote
3answers
64 views

RSA and phi function

I am in process of writing essay about cryptography and math behind it. I know that φ(n)=(p-1)(q-1), but would it be true if p and q are not primes but just ordinary factors of n?
1
vote
1answer
35 views

Find coordinate $y$ of an elliptic curve point

If I have an elliptic curve over a finite filed $F_p$ ($p$ is prime) defined as $$ y^2 \equiv x^3 + ax + b\pmod p,$$ such that $4a^2 + 27b^2 \neq 0$ and suppose I have only given the coordinate $x$, ...
0
votes
0answers
14 views

What is an embedding degree of elliptic curve?

I am dealing with MOV algorithm to transform ECDLP to DLP in $GF(p^k)$, but at the first step I have to determine embedding degree k. I have read the definitions of embedding degree, but still I am ...
4
votes
1answer
47 views

Prove that bitstrings with 1/0-ratio different from 50/50 are compressable

I'm looking for a proof, that $$ \sum_{i=0}^{\lambda n} \binom{n}{i} \le 2^{nH(\lambda)} $$ with $n>0$, $0 \le \lambda \le 1/2$ and $ H(\lambda)=-[\lambda log \lambda + (1-\lambda) log (1-\lambda)] ...
2
votes
1answer
73 views

Primitive polynomials in LFSRs

I need help proving the following theorem. I found it many books but on every single one it says that they omit the proof because it is in every good textbook. THM Let $c(x)$ be a connection ...
1
vote
1answer
468 views

How to add two points on an elliptic curve

How do you add two points P and Q on an elliptic curve over a finite field $\Bbb F_{p}$. For example: adding the points $(1,4)$ and $(2,5)$ on the curve $y^2 = x^3+2x+2$ over $\Bbb F_{11}$. I know one ...
0
votes
1answer
266 views

RSA and calculating huge exponents

I am writing an Extended Essay on RSA encryption and in the essay, I am going through a worked example of all of the stages involved (key generation, encrypting and decrypting). I am using very small ...
0
votes
1answer
22 views

Non-Negligible function arithmetics

Following the other question: If a function is known to be non-neligible by this definition, (for example $q(x)=1/x$, is it true (provable) that $poly(x)*q(x)$ (for ...
0
votes
0answers
25 views

Studying a code in cryptography

So,i'm given a binary code $C$ with it's generator matrix $G=(A,B)$ where $A,B$ are given matrices. The task is to study the code. First question: What does this form $(A,B)$ mean? how would $G$ look ...
0
votes
1answer
31 views

hash function not using bitwise operations

I have a need for implementing an algorithm to validate that a given message is not altered after some operations (for instance after transmission over a medium). A typical way of doing this kind of ...
2
votes
3answers
83 views

can it be proven that something is “difficult” (prime factoring for example)

I understand that the current state of the art suggests that factoring into primes is a difficult problem. I also understand that a large part of public key cryptography seems to be based on that ...
0
votes
1answer
167 views

coding and decoding message with RSA.

First of all, I know how to solve the following exercise; the problem is that there is no solution. "In RSA, Alice chooses $p=53$, $q=63$, public key ($n=3339, e=13$). When Bob sends the message ...
2
votes
1answer
198 views

How to show that the $x^a \equiv 1 \pmod p$ has exactly $\gcd(a,p-1)$ solutions at $Z^*_{p}$?

It is given that $p$ is prime number and $a\ge1$ solution so far: $x^{\gcd(a,p-1)} ≡ 1$ because it known that a group of units of $Z/pZ$ is cyclic and of order $n=p-1$ for $p$ prime, and also in ...
1
vote
1answer
17 views

Probablistic lemma for the Forking Lemma

I am trying to understand the Forking Lemma in cryptography which is a lemma used to prove security of signature schemes by showing that a forging machine can be "forked" (i.e., snapshotted and then ...
1
vote
1answer
26 views

finding $m$ from $c = m^e \pmod{n}$

I'm working through an RSA encryption example, and I'm being asked to solve $c = m^e \pmod{n}$ for $m$ given c, e, and n (along with its factorization.). Since I already have that information ...
0
votes
1answer
43 views

Discrete Logarithm Problem in $GF(p^m)$

I have question regarding DLP in $GF(p^m)$ I know the algorithms for solving the DLP in $GF(p)$ like Baby Step-Giant Step, Pohlig-Hellman etc... But what if we move into the $GF(p^m)$ and are ...
1
vote
2answers
35 views

Discrete log modulo prime

I'm trying to understand properties of the discrete logarithm problem modulo a prime. For a prime $p$, an $\alpha \in \mathbb{Z}_p^*$ and $a \in \mathbb{Z}_{p-1}$ why does $\alpha^x \equiv 1 \mod p$ ...
0
votes
2answers
81 views

Computing p and q from private key

We are given n (public modulus) where $n=pq$ and $e$ (encryption exponent) using RSA. Then I was able to crack the private key $d$, using Wieners attack. So now, I have $(n,e,d)$. My question: is ...
0
votes
1answer
66 views

Public Key Scheme decryption. [closed]

You have been sent a message based on the following Public Key Scheme. 1) Bob chooses two large primes $\ p,q $ with $ p \equiv q \equiv 2 \pmod 3$ and computes $ n=pq. $ 2) Bob chooses integers $ e,d ...
1
vote
0answers
66 views

Solving the discrete logarithm using index calculus, finite fields and factor bases.

(a) Let $p$ be the prime 1073741827, with $\Bbb{F}_p$ the corresponding finite field. A primitive root in $\Bbb{F}_p$ is equal to $g=2$. Use a factor base of primes up to 13 to find the discrete ...
1
vote
1answer
56 views

Proof of an alternative form of Fermat-Euler's theorem.

I want to know a proof of an alternative form of Fermat-Euler's theorem $$a^{\phi (n) +1} \equiv a (mod \; n)$$ when a and n are not relatively prime. I searched some number theory books and a ...
0
votes
0answers
52 views

Factor a big number by Pollard Rho method

How to factor $2^{2^8}+1$ by Pollard Rho algorithm? I have tried this question,but I have no clue. In order to use Pollard Rho, I should know some factor of this number right? But how can I find one?
0
votes
0answers
21 views

How is the table generated for Galois Field?

If I want to generate tables for $01AB\quad 01AB$ for both addition and multiplication, how will it be generated? I am basically confused from this wikipedia example! I hope someone can clear it up ...
2
votes
1answer
23 views

Decision Diffie Hellman in finite fields

Is there an efficient mathematical algorithm for Decision Diffie-Hellman problem in a finite field $F_q$? I have found a detailed analysis of many more involved or specific cases but nothing on the ...
2
votes
1answer
43 views

Is there a cipher that yields two separate but valid results depending on the key?

Suppose the following. Someone wishes to encrypt a message so it is not intercepted. With traditional ciphers, if the key is guessed correctly, the message is revealed. This cipher is similar– ...