Hot answers tagged

15

Kindly, let me know what was the actual problem which leads us to use groups in cyptogrpahy? Well, we use groups and other similar mathematical constructs because: We found there are problems that appeared to be difficult to solve with those groups We found ways to translate the difficulty of solving those problems into the cryptographical strength of ...


9

The Prime Number Theorem proves that there are approximately $\frac{x}{\ln x}$ primes less than any positive integer $x$. There are thus about $\frac{2^{2048}-1}{\ln (2^{2048}-1)}-\frac{2^{2047}}{\ln (2^{2047})}=22.8\times 10^{612} - 11.4\times 10^{612}=11\times 10^{612}$ 2048-bit primes. That's a rather large number, since there are only about $10^{80}$ ...


7

Groups have properties which are useful for many cryptographic operations When you multiply 2 numbers in a cryptographic operation you want the result of the multiplication also to be in the same set. For e.g. if you are multiplying something which fits in a byte (or n bytes) by something similar, you also want the result also to fit in a byte (or n bytes). ...


4

Yes, this stems from elementary school arithmetic: If you multiply two numbers ending in 1 the resulting least decimal digit or result will always be 1. Primality not required. This does not however mean that if the resulting decimal digit is 1 both original primes end in one: e.g 7*3 or any primes ending in 7 and 3 respectively. The best way to break RSA (...


3

Yes we can factor an RSA modulus $n$ given $n$ and $k \cdot \phi(n)$, including where $k$ is a (reasonably) large prime. We just use $f\gets k \cdot \phi(n)$ instead of $f\gets e\,d-1$ in the algorithm of this answer. The algorithm is heuristic, and I do not claim a rigorous proof of the distribution of the runtime. Also, a larger $k$ tends to make it more ...


3

I think you got it backwards: Algebraic structures like rings and groups and fields are the underlying concept of all commonly used types of numbers like the integers, rationals, reals and complex numbers. In algebra it is quite common to do theorems and proofs in the structure with the minimum requirements - so they are valid in a wide range of structures, ...


3

The problem with "why" "Why" is generally an unfortunate question. It is often very hard or impossible to answer. The reasoning goes like this: if you ask "why" a (reasonably complex) thing is like it is, any meaningful answer usually breaks the issue down into subcomponents. Then, you can and need to ask "why" for ...


2

Gaussian integers are numbers of the form $a+bi$, where $i$ is such that $i^2=-1$. If you consider them modulo a prime integer $p$, then: If $p=4k+1$, then $i$ exists in $GF(p)$ and so Gaussian integers simply reduce to $GF(p)$ when working modulo $p$, with the size of the multiplicative group equal to $p-1$. If $p=4k+3$, then $i$ does not exist in $GF(p)$ ...


2

To encrypt a message, in RSA or other encryption schemes, we convert (encode) the messages into bits/bytes arrays that are dependent on the scheme in an invertible way! If you consider only the English letters, with $A=0,\ldots, Z=25$ then you can make the encoding of a sequence of letters $m_0,m_1,\ldots,m_t$ with $$m = \sum_{i=0}^t 26^i \cdot m_i$$ This ...


2

encrypt with the private key, and decrypt with the public key That statement, and the very name privateEncrypt, is incompatible with standard terminology: "public" means known to all and opposes to "private"; and "encrypt" implies transforming some information $X$ into $Y$ in a way such that if $Y$ becomes public, $X$ does not. ...


2

Maybe I can give another answer from the perspective of Multiparty Computation (MPC), which studies the problem of enabling multiple parties to securely compute a function on sensitive data while revealing only the outputs. A very important tool for solving the problem stated above is secret-sharing, which enables distribution of a secret $s$ into $n$ shares ...


2

Write $d$ for the order of an element of $(\mathbb Z/P\mathbb Z)^\times$, we know that $d|P-1$, and that there are at most $d$ elements of order exactly $d$ as they all form roots of the polynomial $t^d-1\pmod p$. Then counting the number of elements of order less than some bound $B$ is less than summing $d$ over the divisors of $P-1$ less than $B$. Taking $...


2

3174654383 is a very small number & can be factored using a lot of different methods. Here is an online factoring page & it factored it in seconds - https://www.calculatorsoup.com/calculators/math/prime-factors.php 3174654383 = 52673 x 60271 The page also explains how it is done. Your n is 32 bit. In actual RSA, n is typically 1024 or 2048 bits & ...


1

I don't think that we currently know how to exploit such structure. The set-up immediately makes one think of Coppersmith's method for factoring RSA moduli with some bits of the factors known. This constructs a two-variable integer polynomial with an unusually small integer solution and uses lattice methods to find the solution. In this case the polynomial $(...


1

A large issue with questions like this tends to be the technical details, so apologies if I come across as particularly nit-picky --- I just do not know how to answer questions like this without pointing out the nits that need to be picked. at least if the activation function is continuous, could carry up to even infinitely many links with just changes in ...


1

If $e$ is not too large, then it is easy. The relation $q = e^{-1} \mod p$ can be rearranged to $qe = 1 + kp$ for some integer $k$; or in other words, $p/q \approx e / k$; that is, $p/q$ is extremely close to a simple rational, and that makes factorization easy.


Only top voted, non community-wiki answers of a minimum length are eligible