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

learn more… | top users | synonyms

-1
votes
0answers
7 views

Hybrid encryption RSA with AES?

A common variant of textbook RSA is the following: During key generation, the modulus N is chosen as usual. We chose e as e := 3 (instead of random). Then d is chosen with ed ≡ 1 mod φ ( N ) (as ...
0
votes
3answers
24 views

RSA decryption problem

(e,n) = (17,323), with ciphertext 185 First compute $\phi(323) = \phi(17*19) = 16*18 = 288$ In order to find the decryption exponent, we must solve 17*d = 1 mod 288 This is equal to $d = ...
0
votes
2answers
19 views

How do I compute Euler phi function efficiently for repeated prime factors?

In RSA decryption problems, you have to compute $\phi(n)$ and then sometimes $\phi(\phi(n))$ quickly. For example, I had to compute $\phi(2^5)$ for one particular problem and it seems to me (for ...
0
votes
0answers
7 views

Particular type of input to gather information on certain types of encryption schemes

Consider a simple case in which information is sent is considered as it's binary equivalent and then those numbers are considered as base 10 and used as inputs to an equation over a number field of ...
0
votes
2answers
24 views

Requested material on Bilinear Pairing

Bilinear map/pairing is widely used in Pairing based Cryptography. I am new to this area. Can anyone suggest me some good reference on Bilinear pairings? I need at least an example of Bilinear map ...
1
vote
1answer
19 views

Computing fractions Weierstrass curves and DLP problem

I am preparing for a crypto exam by making an old practise exam. I got stuck on the following assignment. I got this weierstrass curve The curve $y^2 = x^3$ is not an elliptic curve over $F_{71}$ but ...
0
votes
0answers
16 views

Sequence of Encrypting RSA like Chaum Blinding scheme [closed]

I'd be a noob in cryptography but reading up a little on RSA, I do get some understanding and I want to specifically resolve this issue. UPDATED Lets say we have the following values in place: ...
1
vote
1answer
24 views

Finding all Points on a Edwards curve

I need to find all affine points on the Edwards curve: $x^2 + y^2 = 1 - 5x^2y^2$ over $F_{13}$ I tackle this by transforming the equation to: $y^2 = \frac{1-x^2}{1+5x^2}$ I then go from x = 0 to ...
0
votes
0answers
26 views

Probability theory in (classical) cryptography

In (classical) cryptography we have the formal definition of a cryptosystem that is a quintuple $(M,C,K,e,d)$ where $M$ is the (finite) set of plaintexts, $C$ is the (finite) set of ciphertexts, $K$ ...
0
votes
0answers
13 views

How to determine sub-exponential time growth?

I'm a little bit confused of sub-exponential time growth; consider the definition from Hoffstein's book An Introduction to Mathematical Cryptography: Given input of $k$ bits, then if an algorithm ...
0
votes
0answers
12 views

Proving the CBC mode with one time pad is IND-CPA insecu

I have a hypothetical encryption scheme where somebody uses the one-time pad in CBC mode. That is, the block cipher is E(k, m) :=k⊕m, and that block cipher is used in CBC mode. Now, I am assuming ...
1
vote
2answers
80 views

Number Theory and Cryptography

I am a math tutor at a community college, and I stopped in to ask one of the professors a question about crypto and he lent me a graduate level book on for a full year course in the title of this ...
0
votes
1answer
42 views

Determining if a number is an nth root

I am working on a proof that depends on if an adversary can determine if a number is an $nth$ power for some large prime $p$. My intuition tells me that for a sufficiently large value of $n$ this is ...
2
votes
0answers
21 views

How many commutative block ciphers are there?

Let $K$ and $M$ and be two finite sets. Let $(G,\circ)$ be the group of permutations over $M$ under composition. Let a (implicitly: block) cipher with key in $K$ and message in $M$ be any application ...
1
vote
1answer
26 views

Confused about discrete logarithm question

For purposes of explaining the notation for those unfamiliar, if we fix a prime $q$, as well as $a,b$ nonzero integers $\mod{q}$, $L_a(b) = x$ is the solution to the equation $b = a^x \mod{p}$ We are ...
2
votes
0answers
26 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– ...
2
votes
0answers
11 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 ...
1
vote
2answers
54 views

Find all $n$ such that if $\gcd(a,n)=1$ then $a^2=1$ mod $n$

I really have no idea where to start with this question: Find all $n$ such that if $gcd(a,n)=1$ then $a^2=1$ mod $n$ I found out that it works for $n = 8$, since all odd numbers modulo 8 have order ...
0
votes
0answers
39 views

RSA Decryption - finding Private Key

Let p and q be primes and $e \in \mathbb{Z}^+$, with $\gcd (e, (p-1)(q-1)) = 1$. Let d be the inverse of $e \mod (p-1)(q-1)$. The decrption process where M is plaintext and C is ciphetext ...
5
votes
2answers
145 views

Understanding Intel's white paper algorithm for multiplication in $\text{GF}(2^n)$?

I'm reading this Intel white paper on carry-less multiplication. For now, suppose I want to do multiplication in $\text{GF}(2^4)$. We are using the "usual" bitstring representation of polynomials ...
1
vote
1answer
22 views

Question regarding Monoalphabetic Phi Test

I've been asked to prove the following system of inequalities; $$1 \ge \phi(T) \ge \frac{n-k}{k(n-1)}$$ Where $\phi(T) = \sum_{i=1}^{k} \frac{n_i (n_i -1)}{n(n-1)}$, $T =$ some text, $n = $ length ...
1
vote
0answers
13 views

statistical analysis of discrete (non-uniform) p-values: cryptographical random data test

i'm doing a statistical analysis of a well-known cryptographic algorithm and have hit an anomaly. i need to prove that what i have found is statistically significant. i am taking block sizes of 256 ...
0
votes
1answer
34 views

For P0 close to P1 the relative entropy can be approximated by its series expansion,Why?

I am reading a article (An overview of distinguishing attacks on stream ciphers, Martin Hell · Thomas Johansson · Lennart Brynielsson) about Distinguishe Attacks. There is a approximate equation ...
3
votes
0answers
64 views

derangements and permutations in cryptography

i have a problem that i am having a bit of trouble with; we are given a partial key (missing 11 letters) for a mono-alphabetic substitution cipher and asked to calculate the number of possible keys ...
0
votes
1answer
31 views

Figuring out RSA Encryption from 1 encrypted and decrypted message

Suppose that you have an encrypted message and a decrypted message (just one). M (the public key) and k (the exponent you raise each number to) are public. Does having one copy both version of a ...
0
votes
0answers
26 views

DLP in a Cyclic group

Let q be a prime. G is a cyclic group of order $q^2$. Show that for solving the DLP in G it's enough to solve two distinct DLPs in two groups of order q . --- We are looking for an x such that ...
0
votes
1answer
19 views

Solving a congruence relation equation

I have the following equation: $$ n \equiv M^a\mod(b) $$ where n, a, b are integers, and M is unknow. How do i solve this equation to find the M value. Those a and b are public keys of the rsa ...
6
votes
0answers
35 views

A special case of zero-knowledge computation

This question is inspired by the disappearance of Malaysian Air 370. Let's suppose the plane crashed into the ocean. These are hotly contested waters where various countries (US, China, India, others) ...
1
vote
1answer
101 views

RSA Ciphertext Message.

Hey I'm really stuck and I have to finish soon. Part A Ray, Sam and Todd are lazy, and they have set up their RSA public keys as $(3,nR),(3,nS),(3,nT)$ respectively. We may assume that any two of ...
1
vote
2answers
51 views

Analyzing and decoding ciphertext

I have a worksheet which contains a dozen ciphertexts where the goal is to decrypt the encrypted English sentence(s). No information is given about what the text contains or what cipher methods are ...
0
votes
1answer
41 views

Does reducing 512-bit blocks to 128-bit hashes lead to 1/4 chance of collision?

This is a quote from a cryptography book called Implementing SSL / TLS Using Cryptography and PKI By Joshua Davies. MD5 operates on 512-bit(64 byte) blocks of input. Each block is reduced to a ...
1
vote
0answers
26 views

Single-Digit Errors

I've been assigned the following homework problem: Given an eight digit number $a_1a_2...a_8$ and a check digit $a_9$, $7a_1+3a_2+9a_3+7a_4+3a_5+9a_6+7a_7+3a_8+9a_9 \equiv 0 \mod{10}$ ...
0
votes
3answers
56 views

How large do my $2$ primes need to be to “guarantee” a longevity of security for my RSA-encrypted plaintext?

I am currently attempting to learn RSA. Most of the literature I am using is at least a few years old, if not older. Given the advancements in computing and improvements in attacking RSA, I am wanting ...
1
vote
1answer
74 views

Finding points on an elliptic curve

I have an elliptic curve $$x^3+17x+5 \mod 59$$ $P = (4,14)$ is given and I need to find point $8P$. to calculate $8P$, I first calculated $2P$ by using the equation sigma = 3x^2+a/2y = ...
3
votes
1answer
41 views

How to find multiplicative orders of all elements in field $\Bbb F$ (say $\Bbb F_{13}$)?

I am working on some finite fields and I was referring to some online class material. Is there any way to find the multiplicative orders of all elements in a field $\Bbb F$?
4
votes
1answer
28 views

Part of verifying that the Weil pairing $e_m$ is well-defined.

As part of a homework problem, I need to show that the value of $e_m(P,Q)$ is independent of the choice of a point $S \in E[m] \setminus \{\mathcal{O},P,-Q,P-Q\}$, where $E[m]$ is the collection of ...
1
vote
0answers
35 views

determining the next random number pseudorandom number generator?

I have given 3 numbers let's say basic example x_0=5, x_1=6 and x_2=2 and modulus p is 7, ...
4
votes
2answers
63 views

Is it possible to do elliptic curve cryptography over $\mathbb{Q}$ instead of a finite field?

Whenever I read about elliptic curve cryptography (ECC), the writer always works over a finite field. But as I understand it there is no group-theoretic reason not to use $\mathbb{Q}$ as the ...
1
vote
1answer
66 views

E: $y^2+y=x^3$ an elliptic curve over $F_{2}$. How to prove the number of $E(F_{2^n})$ = $2^n+1$ if n is odd, …

Let E be the elliptic curve $y^2 + y = x^3$ over $F_2$. Prove $ $#E($F_{2^n})$$ = \left\{ \begin{array}{ll} 2^n+1 & \quad n=odd \\ 2^n+1-2(-2)^{n/2} & \quad ...
0
votes
0answers
23 views

Infinite One-Time Pad

As you know, when used correctly, a one-time pad allows one to send a message, such that the only thing that can be found out about it is the maximum size (which is also the key length.) It is ...
1
vote
3answers
53 views

Inverse Totient Function, given $n$ find all possible is for $\phi(i)=n$

I am trying to figure out easy understandable approach to given small number of $n$, list all possible is with proof, I read this paper but it is really beyond my level to fathom, attempt for ...
0
votes
2answers
93 views

Cube roots modulo $p$

Let $a$ be a positive integer. Is there any general method of solving equations of the form $$x^3\equiv a$$ modulo $p$, where $p$ is a prime number? Here are two examples: Example 1: In ...
1
vote
0answers
78 views

Rank of Quadratic Form

Let $n,m, s \in \mathbb{Z}$ be integers satisying $n=s^2$ and $m=2n$. Let $\newcommand{\bigmatrix}[1]{ \begin{pmatrix} #1_1 & #1_2 & \cdots & #1_s \\ #1_{s+1} & #1_{s+2} & \cdots ...
0
votes
2answers
73 views

decoding an encrypted text with modulo

A B C D E F G H I J K L M N O 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 P Q R S T U V W X Y Z Ä Ö Ü ß 16 17 18 19 20 21 22 23 24 25 26 27 28 29 00 A encryption method ...
0
votes
1answer
32 views

Modular arithmetic to find the mod of a large number

If $x \equiv 23 \bmod 317$ and $x \equiv 25 \bmod 331$, what is $x \bmod 104927$? What techniques are typically used to solve problems of this nature? It doesn't seem clear to me that it can be solved ...
1
vote
3answers
60 views

Why does a key have to be at least as long as a message (cryptography)?

I am studying cryptography and find it hard to understand. What happens if the key is one bit or 100 bits shorter than the message?
1
vote
1answer
47 views

Can hash function be considered as linear functional?

I'm not very good in functional analysis or cryptography (so I'm not very sure in what I'm saying): A hash function (as I see it) is some kind of rule that makes an integer from an array (of letters ...
2
votes
1answer
222 views

Prove: b passes the Fermat test for $m = p^2$ if and only if $b^{p-1}\equiv 1\pmod {p^2}$

Question: Let $p$ be a prime and $b$ an integer with $\gcd(b,p) = 1$. Prove: $b$ passes the Fermat test for $m = p^2$ if and only if $b^{p-1}\equiv 1\pmod {p^2}$. I know that if $b^{p-1}\not\equiv ...
0
votes
0answers
18 views

Provide sample matrices that could be keys in the Hill cypher

Well, to encrypt some message I need to multiply parts of it by some matrix key, and to decypher it I need to multiply the output by the inverse matrix. But I've found an excercise to provide some ...
0
votes
2answers
55 views

Plaintext attacks: affine cipher

Consider an affine cipher with encryption function $e$, key $k=(k_1,k_2)$ and some prime $p$. The encryption function $e$ is defined as $e(m)=k_1m+k_2$ modulo $p$, where $m$ is some message ...