regular expression matching on encrypted data using secure multiparty computation Lets consider Secure Multiparty Computation based on Secret Sharing schemes (rather than Garbled Circuits approach). If we have to do regular expression matching on secret shares of words of texts. Trivial solution is to secret share each letter of the word and distribute to different parties and later each party executes the regular expression on the secret shares of each letter.

For example : $SERVER\_01\_LAB$ could be secret shared on each letter "S,E,R,V,E,R,0,1,_,L,A,B" . and for the regular expression $SERVER.*LAB$,  we build secret shares of each letter and send the regex of respective shares to individuals for matching.

But this is too trivial and breaks all the security because if we create secret shares of individual letters then adversary can perform simple frequency analysis on shares and break it .

Can we do this better ?  Any better approaches exist ?

there are some special constructions that could be used. for example see this paper of florain kerschbaum (freely available version).
also, you can use some secure DFA evaluation protocols, as any regex can be represented as a DFA.

what you have proposed is not secure and the servers can learn lots of information.


SHA-1 – Why are text containers used for certificates? Why are researchers using text files to prove the successful collisions?

In the case of the first MD5 collisions I believe it was PostScript-files. In the case of the recent SHA-1 collision it’s PDF files.  A PDF file is basically a container file that comprehends a lot of meta-data attached to the actual viewable data. I presume this complicated the things, not the user readable data itself (the “content” of the PDF the viewer cares about). PostScript sometimes is called the predecessor of PDF and is somewhat comparable.

Why are these kind of “containers” used?

Assumption: apparently there’s enough data next to the actual data we want to change, to do some bit flipping / tricks to generate a collision.

Is this true?

The PDF or PostScript is used so that the collision is made very graphic. It is a public relation tool.

Known collision attacks on hash functions like MD5 and SHA-1 have some restrictions: the attacker can choose most of the colliding pair of messages, but the two blocks where interesting things occur are essentially random, and they will differ by only a few bits. The remainder of the colliding messages will be the same for both messages. So, as plain text, these blocks will be definitely non-pretty, and that's where the collision occurs. Thus, a plain ASCII text demonstration of the collision will not be "convincing" except for cryptographers.

Use of PostScript or PDF allows to leverage that small difference into arbitrarily spectacular differences; basically, the attacker can choose two completely different graphical contents for the whole page.

When the first collisions on MD4 were published, Dobbertin made the effort of making a sort-of ASCII text demonstration. His colliding pair consists in:

********************
CONTRACT

At the price of $176,495 Alf Blowfish sells his house to Ann Bonidea. ...

and:

********************
CONTRACT

At the price of $276,495 Alf Blowfish sells his house to Ann Bonidea. ...

in which the "*****" are twenty ugly-looking bytes that the attacker will claim to be there "for security reasons". MD4 is sufficiently broken that Dobbertin could make a demonstration with such mostly ASCII text, but he still had to include bytes that do not map to meaningful ASCII text.


A clarification about OTR shared secrets - how long need they be secret? A quick question on confirmation/authentication with the OTR protocol.

OTR shared secrets/Q&A when used to authenticate your partner in conversation, am I correct my understanding that they DO NOT need to remain secret after the initial key exchange has finished?

An example of how this might be important, say, Alice asks Bob, who was Best man at Carol's wedding; this is not per se secret, but if Bob can answer quicker than the NSA can, once the NSA figures out who Dave's best man was when he married Carol, is this information useful to them in going back?

My understanding is that it is not and that the shared secret need only be shared at the instant that the key exchange is being done.

Or; if Alice had a function, f(x) that did some computations on x, and could be sure that Bob could do these computations (and/or figure out what the function was) before Eve does; etc.

Responses are much appreciated.
Regards
NTP

Yes.
OTR uses the socialist millionaires protocol, which is an interactive protocol Alice and Bob use to establish confidence that their secrets match (without either of them disclosing the secret). If the authentication succeeded, both parties store the public key fingerprint of the other and mark it as trusted. The shared secret is not used any further (e.g., to derive keys used in later stages), thus knowledge of it is useless to an attacker after the initial authentication step has finished. (That is, after the authentication was done, there is no difference to manually having compared the fingerprints.)

Of course, if Alice and Bob authenticate again at a later point in time (e.g., because one of them created a new key pair), they must not use the same shared secret if it is not secret any more. (This should be obvious.)


What is the purpose of decomposing ciphertext into digits during relinearization in Brakerski Vaikuntanathan homomorphic encryption? In Brakerski and Vaikuntanathan's homomorphic encryption scheme, the relinearization function turns a 3-element cipher back to a 2-element cipher by using a set of public homomorphism keys (https://eprint.iacr.org/2011/405.pdf, see section titled "An Optimization to Reduce Ciphertext Size").

I do not understand the point of encrypting the base-t digits of $c_2$ instead of just encrypting $c_2$ as a whole. Can someone explain? For example, instead of publishing a large set of homomorphism keys encrypting $t^is^2$ (where s = secret key): $$hk_i = (a_i, b_i=-(a_is + te_i) + t^is^2)$$for each i, and making the untrusted server build $c_2s^2$ out of these components, you could just publish a single key $$hk = (a, b=-(as+te) + s^2)$$and have the relinearization operation be $$c_0^{relin}=c_0+c_2b$$ $$c_1^{relin}=c_1 + c_2a$$ and the decryption would yield $$m=c_0^{relin} + c_1^{relin}s$$$$=c_0+c_1s+c_2as + c_2b$$$$=c_0+c_1s + c_2s^2-tec_2$$which, taken mod t, gives the correct result of the homomorphic multiplication. Is there a problem with this much simpler way? Why decompose $c_2$ into digits?

The decomposition helps with the noise growth of your scheme.

You see, the decryption only works if you "error" (here the terms you denote by $e$) is small enough. If $t*e$ grows beyong the modulus (all the computations are done modulo some number, let's say $q$), the mod $t$ operation won't yield the message $m$, but $m$ + $t*e$ mod $q$.

Now when you're multiplying 2 ciphertexts, the errors get multiplied, and they also get multiplied by the plaintext.
Hence, you need your plaintext to be small enough, so $s^2$ cannot be used directly for this reason. When you decompose it in binary, you will have a sum of $log(q)$, but each of those will have a much smaller noise, because they only get multiplied by at most $t$.


Permutation of keys that guarantees different hashes Suppose I have two values to be hashed, $x$ and $y$. Is there a hash function $H$ with the following properties?

$H(x) = H(y), \; H(m(x)) \neq H(m(y))$

Where $m$ is a permutation function that may depend on $H$.

Edit: The corrected question is, if $H(x) = H(y)$, them is it possible to make any permutation $m$ so that $H(m(x)) \neq H(m(y))$?

I assume you're asking whether there exists a hash function $H: \{0,1\}^* \to \{0,1\}^\ell$, and a permutation $m: \{0,1\}^* \to \{0,1\}^*$, such that $$H(x) = H(y) \implies H(m(x)) \ne H(m(y))$$ for all $x \ne y$.

The answer, alas, is no — there is no such $H$ and $m$.

If there was, we could construct a collision-free hash function $H': \{0,1\}^* \to \{0,1\}^{2\ell}$ as $$H'(x) = H(x) \| H(m(x)).$$  But since the set $\{0,1\}^*$ is infinite, while $\{0,1\}^{2\ell}$ is finite, this is clearly impossible.

More generally, the same argument shows that no such $H$ and $m$ can exist if the input domain of $H$ has more than $n^2$ elements, where $n = 2^\ell$ is the number of possible outputs of $H$.


What happens after sharing the secret key in quantum cryptographic schemes to send the message bits? As a person working on the physics perspective of quantum communication, I understand the process upto which the quantum key is shared securely. What happens after this process to send message bits? The literature that I've come across talk about encryption and decryption algorithms and not anything further in detail. Shouldn't the length of the key be equal to the number of bits to be ultimately sent?

The actual "process upto which the quantum key is shared securely" is nontrivial from an information theoretic perspective, to the point that few people understand it fully (I don't), and some do not even realize that prerequisites include a shared secret. See sections A and B in this for an overview, and section E.1 for why we should take the security claims with more than a grain of salt.

What occurs after that Quantum Privacy Amplification (often called Quantum Key Distribution) step depends on the objective:

If we want confidentiality without unproven mathematical hypothesis (as in the previous step), we need as many key bits as data bits enciphered; and some more for integrity. See C.1 in above link.
Alternatively, if we want a fast link, we use classical cryptography with the key established (perhaps, periodically) by Quantum Privacy Amplification. But we must trust the (symmetric) crypto used, despite lack of mathematical proof that it is safe. See C.2 in above link.


Existential Unforgeability of signature scheme against Adaptive Chosen Message Attack While reading a literature on signature schemes, I came across the concept of Existential Unforgeability of signature scheme against Adaptive Chosen Message Attack. Can anyone point me to the  paper where this notion was introduced first? Otherwise, may I ask for a paper/reference where the above-mentioned game is properly defined?

These are standard terms in the cryptographic literature. Refer to Goldwasser's Lecture Notes on Cryptography, particularly section 10.3.1 where the definitions of forgery of digital signatures are introduced:

Existential Forgery: The adversary succeeds in forging the signature of one message, not necessarily of his choice.
Selective Forgery: The adversary succeeds in forging the signature of some message of his choice.
Universal Forgery: The adversary, although unable to find the secret key of the The forger, is able to forge the signature of any message.
Total Break: The adversary can compute the signer’s secret key.

The exact use of these definitions can be seen later in the notes in which some proofs are discussed.


Elliptic curve as a product of 3 cyclic groups possible? I'm looking for some kind of 3-dimensional Elliptic curve. As far as I know a normal Elliptic curve like $$y^2 = x^3 + ax + b$$ over $F_p$ consists of one or two cyclic groups $Z_m (\times Z_n)$. Given one point and one/two generators you can reach each point with it. Now I'm looking for a product of 3 cyclic groups, given a point and 3 generators let you reach each point in this product.
(btw for cryptography do you mainly use elliptic curves with one ore two cyclic groups?)

So lets say it's $Z_m \times Z_n \times Z_r$ with generators $g_m, g_n, g_r$ and a point $s$ which lies in there. With $s g_m^i g_n^j g_r^k$ all points can be reached. E.g. $s g_m^m$ would be $s$ again and $s g_m^i g_n^j = s g_n^j g_m^i$ (same for $r$,$m$,$n$). (Best for use case would be $m=n=r=prim$)

I read from Wikipedia about Projective twisted Edwards coordinates with $$(a X^2 + Y^2)Z^2 = Z^4 + d X^2 Y^2$$

It has 3 coordinates but not sure if it's what I'm searching for. Can't find information about the inner structure.
I did some tests with the written algorithm but it was neither cyclic for all points nor closed for all points nor a product of 3 cyclic groups. I did some test with small numbers ($p,a,d$) and found many different cycle sizes. Normal for that kind of Elliptic curves? Did I something wrong? Is it what I'm looking for?

Do you know any other Elliptic curve with an inner structure of 3 cyclic groups (some more also Ok, can ignore those)?
Or something else which produces 3 cyclic groups, with the condition, given two points, starting at one you don't know how to reach the other point. Only way doing this try around until finding him. So you don't know which generator using next. And if you found him you also know the way backward.

Every elliptic curve over a finite field (and this includes Edwards curves; the use of projective coordinates $(X,Y,Z)$ has no relation to this) is a group isomorphic to $\mathbb{Z}_{n_1} \times \mathbb{Z}_{n_2}$ for two integers $n_1$ and $n_2$ such that $n_1$ divides $n_2$. In fact, if you have a curve over a finite field $K$ such that $r$ (prime) divides the group order, but $r^2$ does not, then there is a field extension of some degree such that, in the field extension, there are $r^2$ points of order $r$, and these points are a subgroup isomorphic to $\mathbb{Z}_r \times \mathbb{Z}_r$. This is probably not what you want.

For an integer $n = pqr$, for three integers $p$, $q$ and $r$ which are prime to each other, $\mathbb{Z}_n$ is cyclic, but it is also isomorphic to $\mathbb{Z}_p \times \mathbb{Z}_q \times \mathbb{Z}_r$. This is what the Chinese Remainder Theorem is about. What this means is that being cyclic does not prevent a group from also being isomorphic to a product of three cyclic groups. In particular, suppose that you have an elliptic curve of cardinal $n$. You can then find points $P$, $Q$ and $R$, of order $p$, $q$ and $r$, respectively, over that curve. Then, the curve will be isomorphic to the product of the three subgroups generated by $P$, $Q$ and $R$, which means that every point $T$ of the curve can be uniquely decomposed as $T = uP + vQ + wR$ for three integers $u$, $v$ and $w$ taken modulo $p$, $q$ and $r$, respectively.

It is unclear whether such a curve is really what you want. In cryptography, a lot of the security relies on a clear distinction between what is doable, and what is not. For instance, in a curve such as the one expressed above, given a point $T$, one can find its component $uP$ (on the first subgroup) as:
$$ uP = ((qr)^{-1} \bmod p)(qrT) $$
but obtaining $u$ from $uP$ involves solving the discrete logarithm over the subgroup generated by $P$, which is hard and basically infeasible if $p$ is large enough. Whether these characteristics are appropriate for your use case depends on what you want to use that curve for.

Building a curve with a specific order $n$ is not easy. You can use supersingular curves; e.g. in the field $\mathbb{Z}_e$ with $e$ prime and $e = 2 \bmod 3$, the curve $y^2 = x^3 + B$ (for some $B \neq 0$) has order exactly $e+1$ points. However, discrete logarithm on that curve is relatively easy (you'd need $e$ to have size at least 1024 bits, which means that operations will be slower than what we usually get with elliptic curves). For non-supersingular curves, Complex Multiplication theory can help: given your target order $n = pqr$, if you can find a prime integer $e$ such that $e = 1 \bmod 3$, and an integer $g$ such that:
$$ 4e - (e+1-n)^2 = 3g^2 $$
then about 1/6th of curves of equation $y^2 = x^3 + B$ over the field $\mathbb{Z}_e$ (for constants $B \neq 0$) will have order exactly $n$. Finding solutions to that kind of equation is not easy and I am unsure there is actually a known method for that.

In any case, a first step would be first to define, precisely, the kind of properties that you need, in particular which relations and transformations need to be feasible, and which must not be feasible, in order to ensure the security of whatever scheme you want to build on top of that curve.


Transition to post-quantum cryptography Classical asymmetric cryptography is commonly based on the Discrete Logarithm Problem and Integer Factorization, which are known to be solvable with a quantum computer if it has the ability to run Shor's algorithm, or an algorithm that solves these is devised to run on a classical computers.

Nowadays we know this is impossible to come at least in a few decades. But that doesn't imply that a passive eavesdropper gathers key exchange handshake packets where the symmetric key is negotiated.

The eavesdropper could decrypt the communications associated with these key negotations once the aforementioned quantum computer is built. For example, in the past, cryptosystems that were being used ended up being vulnerable to attacks so a specialized attacker could recover all the stored private information during years.

The evident matter here is that moving to post-quantum cryptographic schemes in the present would stop an attacker in the future to recover private information once conventional asymmetric schemes are broken. I know these schemes are being analyzed right now i.e NIST calling for new post-quantum crypto schemes.

Q1: Is there any institution or government in the present implementing for example NTRU, SIKE or multivariate crypto schemes on their communication establishment to prevent past private information recovery?

Q2: What would be a good estimation on time (i.e years) to move on to these post-quantum cryptographic schemes? I mean, we cannot wait until these attacks are possible on a theoretical capable quantum-computer.

Question #1:

Is there any institution or government in the present implementing for example NTRU, SIKE or multivariate crypto schemes on their communication establishment to prevent past private information recovery?

Answer:

Currently the Open Quantum Safe (OQS) project has been launched to support the development and prototyping of post-quantum cryptography or quantum-resistant cryptography.

They have implemented liboqs, an open source C library for quantum-resistant cryptographic algorithms based on the selected NIST Round 2 candidates (such as NTRU, SIKE, and MQDSS (which is multivariate crypto scheme) at GitHub repository.

Question #2:

What would be a good estimation on time (i.e years) to move on to these post-quantum cryptographic schemes? I mean, we cannot wait until these attacks are possible on a theoretical capable quantum-computer.

Answer:

(1) The Open Quantum Safe (OQS) project co-leader, Michele Mosca published an article Cybersecurity in an Era with Quantum Computers: Will We Be Ready? in IEEE Security & Privacy (Volume 16, Issue 5, September/October 2018) to "estimate a 1/7 chance of breaking RSA-2048 by 2026 and a 1/2 chance by 2031."

(2) The Closing Remarks of Second PQC Standardization Conference held by NIST in August 2019, NIST PQC Standards - Next Steps states that

“NIST should not be aiming to conclude the process and have standards written by 2022. This is simply too fast to get proper answers.... Much more research is needed.”

(3) NIST will give a presentation at the eighth annual International Cryptographic Module Conference (ICMC20) on April 29, 2020 to report an update on the NIST Post-Quantum Cryptography Standardization process. .

Towards PQC Standardization—An Update

"As we proceed to the third-round selection, this presentation shares what has been learned in evaluating the first and second round candidates. It addresses some critical issues and discusses transition and migration strategies."


Will knowing clear text value behind encrypted data help hacker find password? I am building an Android App where I will be storing some encrypted data in a database. To ensure that the user has entered the right password, I have encrypted my own secret phrase and stored it in the database. Thus, I try to decrypt that using the entered user password to see whether it matches the clear text form.

Given that Android apps can be decompiled, to know my secret phrase, and assume encryption technique be figured out, will it be more useful for a potential hacker to know the clear text? I am using password based key generation (10,000 iterations) to do AES encryption.

OK, so what you are doing right now is the following:

The user enters the password.
It gets run through a PBKDF.
The resulting key is used to verify that a stored string decrypts to "foo bar"
If it does, the derived key is used to decrypt the database.

While this should work and there's no risk with publishing "foo bar" because the data stays inaccessible. It would be a nice idea (from a design point of view) to use a proper verification primitive here. This can be something simple, like verifying that the stored HMAC-value is actually the HMAC of an empty string using the derived key.

While an attacker can swap out said encrypted string in theory, this would gain him nothing with regards to the actual data and only allow him to inconvience the user a bit. Now you could argue that using such a string could inconvience the attacker, but all he would have to do, is to reverse-engineer the application to find the string.

Also note that you must not use the an easier password-based key derivation function for either the password verification or the database decryption because the attacker then gets to chose against which he wants to brute-force.


Is the "Signed on date" of a PGP Signature Verified? I noticed that PGP signatures have a "signed on" field.  I was wondering if this is "trustworthy" information and if so how is it accomplished.

For example, I can't see how it could be trusted because someone could sign something a year ago and transmit it now or they could generate a fake date and I don't see how an outside system could tell whether it was actually signed on the specified date.

So is the signed on date to be trusted or is it just the word of the person who signed it?

The "signed on date" field of any signature message format is only trustworthy if you trust the signer to not

modify the software to include an arbitrary date (or use a software which allows setting the date) or
change his computer's system date.

So, if the signer wants to use this field to prove that this was signed at some time (specially, before some time), it is not trustworthy at all.

There are cryptographic means to certify that some data was signed at a certain point in time, but these use either a trusted third party (a signature service, which signs some digest of your message/signed message/... and a time stamp), or even a distributed system with a public time line.

An example would be something like the BitCoin block chain - for every piece of data referred from a block in the chain (i.e. from a transaction) you can be quite certain that it existed before the block was created, as long as the used hash functions are not broken. On the other hand, if you include in your signed data a hash of the latest block, your data bundle is certified to be newer than this block. (But of course, you could have recreated it later.)


Does the discrete log assumption hold if k > p In discrete log cryptosystems like ElGamal it is noted that the "private key" $k$ should be chosen as any element of the group $G$ i.e. $k < p-1$. Does the integrity of the cryptosystem rely on $k$ being an element of the group or can it be larger as well (always assuming that $g^k \bmod{p}$ will be published in the public key)? If yes, can it be any arbitrarily selected number larger than the group?

Assume that you have chosen a large $k > p$, then one can show that $k'$ with

$$k = \ell \cdot (p-1)+ k' $$ can also be your equivalent key.

From Euler's Totient Theorem, we know that $$a^{\phi(n)} \equiv 1 \bmod n$$ for all $a$ relatively prime to $n$.

If your key $k> p-1$ then we can write it like below with division algorithm - division by $p-1$;

$$k = \ell\cdot (p-1)+ k' = \ell \cdot \phi(n)+ k'$$ Now place this into $a$'s power and use the Euler's Toitent Theorem:

$$a^k \equiv a^{\ell \cdot \phi(n)+ k'} \equiv a^{\ell \cdot \phi(n)} a^{k'} \equiv \underbrace{a^{(\phi(n))\ell}}_{\equiv 1 \bmod p} a^{k'} \equiv a^{k'} \bmod p$$

Therefore we have

$$a^{k'} \equiv a^k \bmod p$$ and by using $k$ you will not achieve any higher security, contrary you will calculate unnecessarily steps in modular powering.

If you want to achieve more security, you should use a larger modulus.


Matsui's paper on linear cryptanalysis - unexplained formula in Lemma 2 How does he end up with this result in his article ?

This is a type of "Gaussian approximation", assuming the wrong key randomization hypothesis, and given the bias $|p-1/2|$, the success probability depends on the order statistics of the "sample bias" of the various subkey bit guesses.

Let $T_i$ be the number of times the linear approximation is satisfied by subkey guess $k_i,$ and $$Y_i=|(T_i/N)-1/2|,$$ is the sample bias corresponding to this subkey guess ($N$ is the number of plaintext/ciphertext-pairs). Let $k_0$ be the right key guess and let there be $2^m$ subkey values possible, say from $0$ to $2^m-1$.

Then linear cryptanalysis is successful if and only if
$$Y_0>Y_i,\quad 1\leq i\leq 2^m-1.$$

This probability is then estimated via a gaussian approximation.

The paper "On Probability of Success in Linear and Differential Cryptanalysis", from the Journal of Cryptology, by A. A. Selcuk available here goes over this in detail.


Proving that a scheme is not IND-CPA-secure Suppose I want to prove that a given symmetric encryption scheme is not IND-CPA secure. The first thing I do is to define a specific adversary that attacks the scheme. How can I proof neatly, (using the game where A chooses two messages and is given a ciphertext $c$) that the adversary indeed almost always can determine which of the two messages is encrypted? So the result must be $Pr[$Game$_A^{CPA}(n)=1]-\frac{1}{2}$ is non-negligible. I get stuck in using the probabilities. Like what exactly does $Pr[$Game$_A^{CPA}(n)=1]$ (where $n$ is a security parameter)mean? Is it $Pr$[A outputs 1 and $c$ is the encryption of message1] + $Pr$[A outputs 0 and $c$ is the encryption of message0]? The output of A (guessing the right message) depends on the ciphertext so I am a bit confused.

Seems like you're getting confused between two different notations. Generally, in the experiment, adversary $A$ will output a bit $b'$. So, we have the following notations which refer to the bit $b'$ output by $A$:
$$Pr[A(n)=1]$$
and
$$Pr[A(n)=0]$$

Now, $A$ is said to have won the experiment if $b'=b$ and that is captured by the following notation. Here, we are interested in the outcome of the experiment.
$$Pr[Game_A^{CPA}(n)=1]$$

The $=1$ in the above should not be confused with $A$'s output. Rather $1$ means $A$ wins (i.e. $b'=b$) and $0$ means $A$ loses (i.e. $b' \neq b$)


How does ECC go from decimals to integers? I realise that elliptical curves are tricky, but there's one aspect that no one seems to explain. I've looked, and it's towards the beginning.  This is the traverse over a red curve:-

This is only three steps (n=3).  For cryptography n must be large. I don't know how large but I cannot believe that all tangential and intersection points occur at coordinates with integer values.  They must be decimal. After all the curve is smooth and continuous.  The tangents can be all sorts of infinitely precise gradients. We know that decimal encryption can't work due to representational and rounding errors. Assume that point G is at (-2,4).  There is no way that point 8G is at (3,3) exactly.  And if n is very large?

I had a look at the wiki article regarding elliptic curve point multiplication, but using an example of 42.57 degrees didn't clear it up any. I think that there's a crucial step I'm missing before the explanation of Integers in ECC. So,

Q: How do traverses over elliptical curves go from decimal coordinates to integer values that can then be used for practical cryptography?

The fact that I've identified this curve as type "red" indicates my lack of ECC knowledge or general mathematics ability.  Is it possible to explain simply or am I reaching beyond my grasp?

I think what's going on is that a lot of introductions to elliptic curves start off with the geometric description of the group laws so as to be as visual as possible (it certainly is not intuitive to me at all). And then they switch to elliptic curves over finite fields, which look very different than the continuous case over $\mathbb{R}$ even though the group laws are the same:

$$y^2 = x^3 - 2 x + 1 \text{ over } \mathbb{Z}_{89}$$

[source]

I know; that doesn't look like a curve at all. So the idea of a "curve" is really weird over a finite field. But doing all of your calculations  $\bmod p$ (i.e., adding points, calculating "slopes") will always be integral.

Let's go through an example using the curve $E: y^2 = x^3 - 2x + 1$ over $\mathbb{F}_{89}$. Picking $x=4$ gives us $y^2 = 4^3 - 2\cdot 4 + 1 = 57 \bmod 89$. Now, in general, to take the square root modulo a prime, you have to use the Tonelli-Shanks algorithm. Understanding this involves some number theory, such as quadratic residues. Here's a Python implementation. So like "regular" square roots, you can get two answers, and it turns out that $\sqrt{57} \equiv \{71,18\} \bmod 89$. So $(4,18)$ may be the point you mean.

Let's demonstrate addition. Let $P = (P_x, P_y) = (4, 18)$ be the point we just found. I'll pick $Q = (Q_x,Q_y) = (15,63)$. (I iterated through all $x$ from $1$ to $88$ and computed $y$ as above with the modular square root, and just picked one.)

The slope is $\lambda = (Q_y - P_y)\cdot (Q_x - P_x)^{-1} =  45 \cdot 11^{-1} = 45 \cdot 81 \bmod 89 \equiv 85 \bmod 89$

($81$ is the modular inverse of $11$, $\bmod 89$.)

Now calculate $\nu = P_y - \lambda P_x = 18 - 85\cdot 4 \bmod 89 \equiv -322 \bmod 89 \equiv 34 \bmod 89$, and finally,

$$x_3 = \lambda^2 - Q_x - P_x = 85^2 - 15 - 4 \bmod 89 \equiv 86 \bmod 89$$

$$y_3 = -(\lambda x_3 + \nu) = -(85 \cdot 86 + 34) \bmod 89 \equiv 43 \bmod 89$$

So we have $P + Q = (86,43)$ on $E(\mathbb{F}_{89})$. You can check that this point is on the curve since $86^3 - 2\cdot 86 + 1 \equiv 43^2 \bmod 89$.

You may like exploring these ideas with Sage as well.


Split hash for 2 keys These are the steps:

Hash ECDH shared secret with SHA3-512
Concatenate odd bytes and rehash with SHA3-512 for AES-256 key
Concatenate even bytes and rehash with SHA3-512 for KMAC key

Is this key derivation secure? If not, what are the weaknesses?

The key derivation process you describe is reasonably secure in a technical sense, but not a good choice—it's not very flexible, it will raise auditors' eyebrows, and SHA3-512 is just not a good design.

Security if we model SHA3-512 as a uniform random function $H$:
Each of the 512 bytes of $H$ on distinct DH secrets is independently uniform random, so the string of 256 odd-position bytes is uniform random and the string of 256 even-position bytes is independently uniform random.  The probability of collision between the even-position bytes and the odd-position bytes is negligible, and in the event of no collision, the resulting keys are independent uniform random.

Why is it a bad choice?

It's not very flexible.
What happens when you want to derive another key?  You've used up all the bytes (or, most of them, anyway); you'll need to find a different mechanism for this purpose, and it'll be another ad hoc thing that the remaining reasons still apply to.  This fragility may hurt security: Will your successor who needs to extend the protocol make a decision that remains secure?
It will raise auditors' eyebrows.
This is not a standard construction for key derivation.  By adopting this, you make an auditor's job harder by forcing them do cryptographic reasoning like the paragraph above, which auditors would rather not do.  They don't want to think about the even-position and odd-position bytes of a SHA3-512 hash.  They'd rather spend their effort simply confirming that you're using a well-studied and well-understood construction without having to think about it, so they can move on to higher-level protocol issues that will actually be more important in assessing the security of your application.
SHA3-512 is just not a good design.
SHA3-512 pays extra for an unimaginably high security level that doesn't matter to you for two reasons:

Collision attacks are not relevant to your application, but SHA3-512 pays a premium for collision resistance.
For political reasons rather than technical reasons, SHA3-512 was overdesigned to meet a meaningless security target.

General advice aside: Ignore SHA3-256 and SHA3-512.  Use SHAKE128 (with sufficiently long outputs) for a 128-bit security level.  Use SHAKE256 only if you're a paranoid worrying about hedging against modest cryptanalytic advances, like for use with Ed448.

So what should you do instead?  Here are a couple options:

Use HKDF with your favorite hash function.  SHA-256 is a perfectly respectable choice.  If you insist on using SHA-3, you could use SHA3-256, but SHAKE128-256 would be faster for essentially same security—or you could just use SHAKE128 or KMAC128 directly, below.

HKDF comes in two stages, which some APIs weld together:

HKDF-Extract takes initial key material and a salt and hashes them into a master key.

The initial key material is a high-entropy but possibly nonuniform secret, like the outcome of a DH key agreement.
The salt is optional; if it is merely distinct for each user, then it serves to mitigate multi-target attacks.  For a DH key agreement that already achieves a 128-bit security level, like X25519, this is not necessary.  But it doesn't hurt.
The master key is a short secret bit string that is effectively uniform random.

\begin{equation*}
    k_{\mathrm{master}} = \operatorname{HKDF-Extract}(\mathit{dhsecret})
  \end{equation*}

You must never reuse the same initial key material.  (Actually, in practical terms, if you reuse it with distinct salts, you won't get into security trouble—but you will make the auditor's job harder which will make your life harder and hurt your user's confidence in your system.)
HKDF-Expand takes a master key and an info parameter that uniquely describes a purpose and derives a subkey from them.

The master key is what you got out of HKDF-Extract.  (Aside: It could also be from a password hash like Argon2 or PBKDF2, or any short uniform random secret key that you got from somewhere else and you just want to derive multiple subkeys from.)
The info parameter distinguishes the subkeys for different purposes: for each distinct info, there is an effectively independent uniform random subkey; it is as if you generated the subkey independently, but you can get it deterministically and reproducibly from the master key by passing in the same info.
The subkey is what you then use as an AES-256 key or whatever.

\begin{align*}
    k_{\mathrm{AES}} &= \operatorname{HKDF-Expand}_{k_{\mathrm{master}}}(\text{‘AES encryption key’}), \\
    k_{\mathrm{KMAC}} &= \operatorname{HKDF-Expand}_{k_{\mathrm{master}}}(\text{‘KMAC authentication key’}).
  \end{align*}

You must never reuse the same info parameter for two different purposes.  The auditor will want it to be easy to confirm that every purpose for which you derive a subkey has a distinct info parameter, so you should clearly document what each info parameter is used for, and if you ever programmatically format info parameters, make sure that you use a unique encoding of whatever data you put in them to ensure they will be unique.

Use KMAC128, or SHAKE128, directly.
For KMAC128, you can safely just feed in the DH secret as the KMAC128 key, and uniquely encode the salt and info parameters as the KMAC128 message.  Similarly, you could also just uniquely encode the DH secret, the salt, and the info parameters as the SHAKE128 message: $\operatorname{SHAKE128}(\text{32-byte DH secret} \mathbin\| \text{32-byte salt} \mathbin\| \text{‘AES key’})$.

This may be simpler for your application, and it doesn't hurt security.  As long as it's conceptually structured the same way as HKDF—never reuse a DH secret except with distinct info parameters—it should be straightforward for an auditor to follow.


Is Paillier a stream or block encryption Does Paillier follow a stream encryption or block encryption technique.
If it’s a block encryption then what is the size of the block in bits or bytes.

Stream Ciphers
A stream cipher produces key streams usually small sizes as bits (or bytes or words,...) that are x-ored with the message bits to produce the encrypted stream ( or call it the ciphertext). A stream cipher stores an internal state and updates it for the next output. They are also called state ciphers since the encryption depends on not only key and plaintext but also the state.
More formally; let $s$ be the state, $f$ is the next state function, $g$ is the function that produces the keystream $z_i$,  and $h$ is the function that produce encryption of $m_i$ with the key stream $c_i$.
\begin{align}
s_i &= f(s_i,k)\\
z_i &= f(s_i,k)\\
c_i &= h(z_i,m_i)
\end{align}
Block Ciphers
A block cipher operates on blocks and more formally it is a family of permutations. We need a mode of operation to operate on data; CBC, CTR, GCM, etc... There is no stored information inside the block cipher and they are called memoryless ciphers.
More formally: A block cipher with $b$-bit block size is a family of permutations;
$$E:\{0,1\}^b \times \{0,1\}^k \to \{0,1\}^b$$ where each key $k\in \mathcal K$ selects a permutation form all permutations of $\{0,1\}^b$
We expect that this family of permutations forms a Pseudo-Random Permutation (PRP).
Block vs Stream
The distinction is not clear when a mode of operation like CTR mode turns a block cipher into a stream cipher (normally CTR mode is designed for PRF, not for PRP). One, however, can see the real distinction is that if a cipher designed as a stream cipher then it has internal states.
Paillier
Pailler is neither a block cipher nor a stream cipher, it is a public key system in which you need two keys; the public key and private key.
In the Paillier cryptosystem, the encryption of $m$, $0 \leq m < n$ is performed with a public key $(n,g)$ as $c=g^m r^n \bmod n$, where $r \stackrel{R}{\leftarrow}\mathbb{Z}_n^*$.
The message is recovered wiht the private key ($\lambda,\mu$) as $m = L(c^\lambda \bmod n^2) \cdot \mu \bmod n$ where $L = \dfrac{x-1}{n}$.
Long messages with Paillier
If you want to encrypt long messages for a target $A$ with Paillier, then you can divide it into parts where each has at most length $<n$ end encrypt each target with the public key of $A$ with a new random $\lambda$ per block. The problem is tracking the order of the parts. It can be achieved either externally or internally. Externally is clear, internally you must leave some space for the tacking. Still, I will not call this block cipher. Can CBC like encryption be performed, yes and keep in mind to not reuse the $\lambda$
Turning into a stream cipher is also possible but has dangerous paths. Consider using as CTR mode. You need to select a nonce and a counter and encrypt it and then x-or the block with the output. If you omit the generate a new  $\lambda$ for each block, this is going to be a catastrophic failure.
Lack of
Still, there is no integrity and authenticity. The Paillier cryptosystem is malleable by design, remember public key encryption is free and the Paillier cryptosystem has additive and multiplicative properties. Therefore one needs at least HMAC.
Forget it
Remember, we don't use public-key cryptography for encryption, we prefer/advise using hybrid-cryptosystem like DHKE/AES-GCM. Public-key cryptography is slow compared to symmetric encryption. AES has tremendous speed with the hardware support and even GCM has, too. ChaCha20 is very fast even without hardware support. Stick to advice and use a hybrid cryptosystem.


What are the advantages and disadvantages of Merkle signatures over Lamport signatures? I know they are both hash-based and post-quantum secure, and that Lamport signatures can form the basis for a Merkle scheme, but what do you actually gain over standard Lamport signatures by doing this? To put it another way, since Merkle signatures make use of another one-time signature scheme, why would someone use Merkle signatures when they have a perfectly fine one-time signature already?

why would someone use Merkle signatures when they have a perfectly fine one-time signature already?

Because Merkle signatures are not one-time.  Instead, you can use a private key to sign a number of messages. There is a finite limit, however that limit is potentially large.


Could this "symmetric RSA" scheme provide key compromise resistant communications? This question, and fkraiem's answer to it, made me wonder about the security and practicality of using "symmetric RSA" to provide a partially compromise-resistant secure channel.

Specifically, assume that Alice and Bob wish to communicate securely over an untrusted network, so that others cannot read or forge their communications.  Obviously, assuming that Alice and Bob can establish a shared secret in advance, they can achieve this simply using any standard IND-CCA2 secure symmetric authenticated encryption scheme.

However, let's assume that Alice and Bob also wish to minimize the impact of either party's key material being compromised; specifically, even if an attacker learns Alice's key(s), she should not be able to read messages sent by Alice to Bob or forge messages from Bob to Alice, and vice versa.

As I noted in my answer to the linked question, this can be achieved by combining public-key encryption and digital signatures: basically, Alice and Bob each generate an encryption key pair and a signature key pair (i.e. four key pairs in total, for two-way communication), exchange the corresponding public keys, and encrypt and sign their messages.  However, fkraiem gave an alternative suggestion involving just a single RSA key pair, which I interpret as follows:

Alice and Bob together generate an RSA modulus $n$, i.e. a product of two large primes $p$ and $q$.
They select a random exponent $e_A$ coprime to $\lambda(n) = \operatorname{lcm}(p-1,q-1)$, and let $e_B \equiv e_A^{-1} \pmod{\lambda(n)}$.
Alice stores the modulus $n$ and exponent $e_A$, while Bob stores $n$ and $e_B$.  Both erase all other intermediate values, including $p$, $q$ and the other exponent.
To send a (padded) message $m$ to Bob, Alice encrypts it as $c \equiv m^{e_A} \pmod n$, and transmits $c$ to Bob.  To decrypt the message, Bob computes $c^{e_B} \equiv m^{e_A e_B} \equiv m \pmod n$.  Similarly, Bob can send messages to Alice in the same way, just swapping $e_A$ and $e_B$.

Obviously, this scheme will not be secure for arbitrary unpadded messages, for the same reasons that textbook RSA isn't secure.  That said, it might be possible to combine this with a suitable randomized padding scheme to make it secure, although I'm not sure if any of the standard RSA padding schemes would work here; all the RSA padding schemes I know of are meant for either encryption or signatures, whereas this scheme would seem to effectively require both at once.

Thus, my questions would be:

Can this scheme work at all, or is there some generic attack that breaks it regardless of padding?
If this scheme can be made secure using a suitable padding scheme, what would such a padding scheme look like?

(I was hoping it might at least be possible to make this system work in key encapsulation mode, but that seems to be trivially vulnerable to bidirectional forgery if one party's key is compromised: if Eve knows Alice's key, she can not only forge messages from Alice to Bob, but can also intercept any message sent by Bob, decrypt it to learn the encapsulated ephemeral key, and then use this key to send any message she likes to Alice.  So that, at least, would seem to be a non-starter.)

Yes, this seems to make sense and it is a plausible solution. The KEM approach does not work, unless you use some tricks, like including a hash of the message in the KEM. (That could work, of course.)

Security goal

The type of scheme we are looking at consists of three algorithms $(K,E,D)$. The key generation algorithm $K$ outputs two keys, say $k_0$ and $k_1$. The encryption algorithm $E$ takes as input a key and a message and outputs a ciphertext. The decryption algorithm $D$ takes as input a key and a ciphertext and outputs a message or $\bot$.

We require that for any $(k_0, k_1)$ output by $K$ and any message $m$, $$D(k_{1-\beta}, E(k_\beta, m)) = m \text.$$

There are two goals here, confidentiality and integrity. You want messages encrypted with $k_\beta$ to be confidential to everyone who does not have $k_{1-\beta}$. And someone who does not have $k_\beta$ (but may have $k_{1-\beta})$ should not be able to create ciphertexts that look as if they were created with $k_{\beta}$.

Confidentiality

In the confidentiality game, the simulator generates a key pair $(k_0, k_1)$ and gives $k_1$ to the adversary. The adversary chooses two messages $m_0$ and $m_1$. The simulator flips a coin $b$ and creates a ciphertext $c^*$ as $E(k_1, m_b)$. The simulator sends $c^*$ to the adversary, and the adversary eventually sends $b'$ to the simulator. During the entire process, the adversary is allowed to send messages or ciphertexts to the simulator, and the simulator responds with the result of $E(k_0, m)$ or $D(k_0, c)$, respectively.

The adversary wins if $b=b'$. He should not win significantly more (or less) often than half the time.

Integrity

In the integrity game, the simulator generates a key pair $(k_0, k_1)$ and gives $k_1$ to the adversary. The adversary is allowed to send ciphertexts and messages to the simulator, and the simulator responds with the result of $E(k_0, m)$ or $D(k_0, c)$, respectively. Finally, the adversary sends a ciphertext $c^*$ to the simulator and the simulator decrypts it using $k_1$.

The adversary wins if the $c^*$ decrypts correctly and it was not created by the simulator. The adversary's success rate should be negligible.

Analysis Proposal

I would try something like OAEP+, but for simplicity, I would "personalize" the hash functions so that we can use different random oracles for the two senders. The confidentiality game looks a lot like the usual RSA-OAEP+ game, but you need to create ciphertexts for the recipient. This becomes much easier when you use separate random oracles.

I suspect it will work out. It may even be possible to "reduce" the security to that of ordinary RSA-OAEP+.


How rotate RSA keys and how work with old encrypted data I am planning to use the RSA for encryption my data and I am wondering - I've generated the keys pair with some limited expiration time and I will use this private and public keys for the purpose of encryption and decryption and in one time the certificate will be expired. How can I use the new certificate? What is the best scenario if my old certificate is expired and I want to have an access to my old encrypted data - Do I need to re-encrypted all my old data with new certificate or what is the best practise for that?

I've generated the keys pair with some limited expiration time and I will use this private and public keys for the purpose of encryption and decryption and in one time the certificate will be expired

first - do you have a particular reason why would use short lifetime for the keys? Often there is no reason for that.  still  there should be a way how to replace the pki keys when needed.

From the comments seems you are designing a new system, what gives you more flexibility. I will try to build an answer from the comments

RSA has some limitations.  You can encrypt only data shorter than the keysize and as someone already mentioned in another answer - RSA is good at hiding random-looking data.

How PKI (RSA) is used to encrypt data - usually a random symmetric key is generated to encrypt the data (with arbitrary length using a symmetric cipher) and RSA is used only to encrypt (wrap) the symmetric key. see the hybrid cryptosystyem

  what alg do you recommend for symetric encryption?

you have plenty to choose... try to type openssl list-cipher-algorithms  something standard would be good, just don't reinvent anything own. AES-128-CBC could be good start

  Is it possible decrypt the symmetric key with expired certificate (private key)?

now - a homework for you. find out what is difference between a certificate and a public key..

nothing prevents you to use the public key to en(de)crypt even the certificate is expired.


Existential unforgeability vs strong unforgeability In the article https://crypto.stanford.edu/~dabo/pubs/papers/strongsigs.pdf there are two definitions for the security of a digital signature scheme: existential unforgeability and strong unforgeability. The difference is that while in the "existential" condition is fulfiled only if the attacker cannot forge a signature on a message he did not ask the signature for. in the case of "strong" he even cannot generate another signature for a message he already ask for. So, is there an example to a signature scheme which is "existential" unforgable but not strong unforgeble?

It is easy to construct a signature scheme that is existentially unforgeable but not strong. All you have to do is add a bit to the end of a strong scheme, and ignore it upon verification. This enables an attacker to flip a bit and have the new signature accepted. In some "real" settings this arises as well. For example, with ECDSA, a signature $(r,s)$ can be modified to $(r,q-s)$ and it will still be accepted (where $q$ is the group order). This can be prevented by forcing $s<q/2$, but the original signature is indeed not strong.


Perfect Secrecy prove There was a question on my final exam, but I could not get a point. I really want to know the right answer.

Question is:

  Suppose a cryptosystem has perfect secrecy.
    Prove that H(P|C) = H(P)

H(P|C) is conditional entropy.

Mathematically, this is expressed as H(P)=H(P|C), where H(P) is the entropy of the plaintext and H(P|C) is the conditional entropy of the plaintext given the ciphertext C. This implies that for every message P and corresponding ciphertext C, there must be at least one key K that binds them. Mathematically speaking, this means |K| >=|C| >= |P|. In other words, if I need to be able to go from any plaintext in message space P to any cipher in cipher-space C (encryption) and from any cipher in cipher-space C to a plain text in message space P (decryption), I need at least|P|=|C| keys (all keys used with equal probability of  1/|K|to ensure perfect secrecy).


Why is Triple DES not vulnerable to meet in the middle attacks? Consider the Triple DES encryption calculated as:

$$C=  E_{K_1}(D_{K_2}(E_{K_1}(P))).$$

For a chosen plaintext attack, given plaintext $P$, we compute the result of $D_{K_2}(E_{K_1}(P))$ and store it as a table of length $2^{112}$, then decrypt the cipertext $C$ using $2^{56}$ possible $K_1$. I think we also have a meet-in-the-middle attack here; and the computation complexity is also $2^{56}$ as in DES. Is this right? But then why does the literature say that 3DES is more secure than DES?

The computational complexity of the attack you describe is $2^{112}$, since that's how much work it takes to build the look-up table.

In fact, for standard 2-key 3DES like you describe, an attacker capable of building such a look-up table could just as well store $C = E_{K_1}( D_{K_2}( E_{K_1}( P )))$ instead of just $D_{K_2}( E_{K_1}( P ))$ in the table, allowing them to skip the second half of the meet-in-the-middle attack and just directly look up $(K_1, K_2)$ in the table, given a ciphertext block matching the plaintext $P$.

However, the attack your describe (and variants of it) is precisely the reason why three layers of DES encryption cannot provide more than 112-bit security, even though, naïvely, using 3-key 3DES with $C = E_{K_3}( D_{K_2}( E_{K_1}( P )))$ would seem to offer 168 bits of key-space.


Difference between a Polynomial Opening & a Polynomial Commitment Going through the literature led me to think I understood the difference between these two things, but thinking about I am not actually certain. Could you help me correct my definitions of these two things (or provide some more detail that aids understanding)?
Polynomial Commitment: This is an object created by evaluating the polynomial at a specific point. We are in a sense committed to the polynomial because the object was created using the structure of the polynomial.
Polynomial Opening: Revealing what a polynomial is, we open up the polynomial to be seen. We can for example use this to check a commitment.
For some context, taking the KZG polynomial commitment scheme, a polynomial commitment to $f(X)$ is $C = g^{f(\alpha)}$, where $\alpha$ is random and $g$ is the generator of some group. A polynomial opening is then just a presentation of $f(X)$?

A Polynomial Commitment is a cryptographic object that binds a party, typically the prover, to a single polynomial. This object could be

an elliptic curve point, such as in KZG or Bulletproofs
en element of a group of unknown order, such as in DARK
the root of a Merkle tree of a Reed-Solomon codeword, such as in FRI.

The point is that underlying this cryptographic object there is a polynomial $f(X)$ that cannot be changed.
A Polynomial Opening of a commitment is the raw polynomial that the commitment represents, together with any auxiliary information needed to verify that the commitment is well formed and indeed a commitment to the given polynomial. The auxiliary information could be a randomizer in the case of semantically secure commitments, or information that is specific to the mechanics and mathematics of the commitment scheme.
The notions Polynomial Commitment and Polynomial Opening suffice to define the desired security property: Binding. Informally, it states that no realistic adversary can produce one commitment with two openings to different polynomials. More formally, for all probabilistic polynomial time adversaries $\mathcal{A}$, the probability that $\mathcal{A}$ outputs $(C, f_1(X), \mathit{aux}_1, f_2(X), \mathit{aux}_2)$ such that $f_1(X) \neq f_2(X)$ and $\mathsf{Verify}(C, f_1(X), \mathit{aux}_1) = \mathsf{True}$ and $\mathsf{Verify}(C, f_2(X), \mathit{aux}_2) = \mathsf{True}$, is negligible as a function of the security parameter.
Polynomial commitment schemes are only interesting when they come with an Evaluation Proof, which is a proof system that establishes that the value of the polynomial $f(X)$ in a point $z$ equals $y$, i.e., $f(z)=y$, where $f(X)$ is the polynomial that the given commitment $C$ commits to. Note that the verifier in this proof system does not need to know a full description of $f(X)$. In fact, polynomial commitment schemes are used precisely in a context where it would be too expensive for the verifier to read $f(X)$ from a complete description, let alone verify $f(z) = y$ directly.


Maximum length in bits of the product n=pq If p and q are two 1024-bit prime numbers, would the maximum length in bits of product $n=pq$ be ${1024}^2$ or $2^{1024}$?

I think it is ${1048576}={1024}^2$?

Also, would the least significant bit of $n$ be a $0$ or a $1$? I am assuming it would be $0$? Any explanation of what determines significance would be great

If $p$ and $q$ are 1024-bit primes, then by definition of the bit size of an integer (at least, a prime in a cryptographic context with glimpses of RSA), $2^{1023}\le p<2^{1024}$ and $2^{1023}\le q<2^{1024}$. Thus their product $n=pq$ verifies $2^{2046}\le n<2^{2048}$, and $n$ is a 2047-bit or 2048-bit integer. We show by exhibition that both cases are possible, with $p=q=2^{1023}+1155$ for the first case, and $p=q=2^{1024}-105$ for the second.

Hence the maximum length in bits of the product $n=pq$ is $2048=2\cdot1024$.

This generalizes to: for odd primes $p$ and $q$, the maximum length in bits of the product $n=pq$ is the sum of the bit length of primes $p$ and $q$; proof that this bound is tight can be obtained from the observation that $\forall k>1,\exists p\text{ prime with }2^{k-1/2}<p<2^k$, which itself follows from stronger versions of Bertrand's postulate.

Since $p$ and $q$ are large primes, they are odd, hence $pq$ is odd, hence the least significant bit of $n=pq$ is 1.

Addition: in common RSA key generation standards FIPS 186-4 appendix B.3 and ancestor ANSI X9.31-1998, it is chosen primes $p$ and $q$ with $2^{k-1/2}<p<2^k$ and $2^{k-1/2}<q<2^k$, which insures that $pq$ is exactly $2k$ bits.


Formal definition of (perfect) forward security/secrecy In recent weeks the concept of (perfect) forward security/secrecy has
been mentioned a lot, primarily in the context of the shocking
revelations about NSA eavesdropping. As far as I'm aware, this concept
was introduced by C. G. Günther in [1].  Unfortunately [1] only sketches
the concept but does not give a security definition.  The survey [2]
gives a formal security definition only for forward secure
pseudo-random generators. The textbooks [3, 4, 5, 6] all don't even
mention the concept, and the relevant Wikipedia article is near
unreadable.

Could somebody please point me towards a formal definition of
(perfect) forward security/secrecy?

C. G. Günther, "An Identity-based Key-exchange Protocol".
G. Itkis, "Forward Security: Adaptive Cryptography: Time Evolution".
J. Katz, Y.   Lindell, "Introductin to Modern Cryptography".
O. Goldreich, "Foundations of Cryptography".
J. Hoffstein, J. Pipher, J.   H. Silverma, "An Introduction to Mathematical Cryptography".
D. R. Stinson, "Cryptography: Theory and Practise".

Do you have a specific application domain in mind?
I do not know of any formal definition that spans multiple application domains.

A formal definition of Perfect Forward Secrecy for the domain of key exchange protocols is included in this paper:

Beyond eCK: Perfect Forward Secrecy under Actor Compromise and Ephemeral-Key Reveal


Is there a way or how to predict the output size as a result of encryption? Is there a way or how to predict the output size as a result of encryption from 3DES, AES-128, AES-192 etc ? So that I know how to store them in the data in DB given a known possible clear text length.

This depends on:

Precise choice of encryption algorithm
Choice of representation for the ciphertext
Size of additional metadata stored with each ciphertext

On #1, 3DES, AES128, AES192 are block ciphers, so they're not ready-to-use end-user variable message length encryption algorithms.  You use them in the context of some mode, which you should really think of the "real" encryption algorithm.  For example, one very common mode nowadays is GCM (Galois Counter Mode), which instantiated with AES we would call AES-GCM.  Some modes require ciphertexts to be a multiple of the block cipher block size as well, which means that plaintexts get padded to fill up a block.

So first and foremost, the size of a ciphertext depends on the mode.  AES-GCM ciphertexts, in binary, are generally 16 bytes longer than the plaintexts.  And you may need an additional 12 bytes to store the nonce.

Now, #2 ("choice of representation for the ciphertext"): ciphers operate on binary data and produce binary output.  But many systems and developers are very allergic to binary data and prefer all data to be in some sort of plain-text format (e.g., XML, JSON).  So the raw binary output of a cipher is in practice often encoded into ASCII using a binary-to-text encoding like Base64.  This adds about a 33% overhead over raw binary size.

Point #3 ("size of additional metadata stored with each ciphertext"): Often you want to store additional information with each ciphertext, for example metadata related to key management:

A key identifier that allows you to locate, for each ciphertext, the key that was used to encrypt it.
An encrypted data encryption key (DEK).  This is part of a common key management strategy where ciphertexts are encrypted with an ephemeral DEK key, which is then encrypted with a master key (a key encryption key or KEK), and the encrypted DEK is stored alongside the ciphertext.

So you need to work out a number of details to get a precise answer to your question.


How many collisions (identical pairs) are possible in meet in the middle attack on double DES with two unique keys? I was reading my professors slides, I understand how meet in the middle works, but I have a few confusions. So we need two $\{(P_1, C_1), (P_2, C_2)\}$. Let $\lg{(k_1)} = \lg{(k_2)} = 56$, we generate $2^{56}$ of the $X = \{x_i = E_{k_{1,i}}(P_1)\}$ and $2^{56}$ of the $Y = \{y_i = D_{k_{2,i}}(C_1)\}$. So far it took us $2^{56}+ 2^{56}= 2^{57}$ steps to compute $X, Y$.
My understanding is that this is why we say that double DES only increases security by one bit?
Now our job is to find all $x_i,y_j$ such that $x_i = y_j$. I suppose we can use $2^{56}$ binary searches so we could do this in $2^{56}\lg{2^{56}}= 2^{56} \times 56$ steps?
Total steps are now:
\begin{align*}
2^{57}+(2^{56} \times 56) &= 2^{57}+(2^{56} \times (2^5+24)) \\
&=  2^{57}+(2^{56+5} + (2^{56}\times24)) \\
&=  2^{57}+2^{61} + (2^{56}\times24) \\
&=  2^{61}+2^{57} + (2^{56}\times24) \\
\end{align*}
Now we worry about how many candidate paires do we have to check on the second plaintext ciphertext pair $(P_2, C_2)$. This depends on how many collisions we saw from the previous step.  On average the probability is that $x_i = y_j$ is $1/2^{56}$ right? Here is one of the confusions, the slides I am reading say that it is $1/2^{64}$. Since I can't see why, for now I'll proceed with $1/2^{56}$. So the average number of collisions thus must be,
$$
\frac{2^{112}}{2^{56}} = 2^{56}
$$
So now we have to check the $2^{56}$ candidate pairs on $(P_2, C_2)$ meaning the average number of steps are now:
$$
2^{61}+2^{57} + (2^{56}\times24) + 2^{56}
$$
But the slides do this analysis like this, they say there are $2^{64}$ many $x_i$ thus the candidate checks are $2^{112-64} = 2^{48}$. This is followed by this slide which is entirely lost on me:

Could someone offer some clarification?
EDIT: I think I see my oversight, the $|X| = |Y| = 2^{56}$ are subsets of the exhaustive $|X'| = |Y'| = 2^{64}$ sets because $\lg{(x_i)} = \lg{(y_i)} = 64$. Hence $X, Y$ were sampled using encryption decryption. Therefore, when we calculate the collision probablity, we use the cardinalities of the $X', Y'$ yielding $1/2^{64}$.
Is this right?

Now our job is to find all $x_i,y_j$ such that $x_i = y_j$. I suppose we can use $2^{56}$ binary searches so we could do this in $2^{56}\lg{2^{56}}= 2^{56} \times 56$ steps?

Actually, you're more likely to go with a hashing-based approach (which doesn't scale at O(n log n)), or a disk-based sorting approach (which is technically O(n log n), but a rather better constant of proportionality than repeated binary search); a binary search approach would run into a lot of cache misses (assuming you had that much memory).  On the other hand, sifting through that much data is a tad on the nontrivial side, and one we generally ignore when doing this high-level analysis; we simplify the problem by assuming that all computations, aside from the DES evaluations themselves, are "free".
And, the 'steps' involved with doing this search for duplicates are quite a bit different than performing a DES operation (and are likely to be considerably faster); that makes it difficult to sum them meaningfully.
However, to get your real question:

on average the probability is that $x_i = y_j$ is $1/2^{56}$ right?

Nope; it's $2^{-64}$; that's because both $x_i, y_j$ are 64 bits, and can be assumed (with an incorrect key) to act completely random.

So now we have to check the $2^{56}$ candidate pairs

Nope; there are about $2^{112} / 2^{64} = 2^{48}$ expected
That should explain where the slide is coming from.


What are the advantages of MICKEY over Trivium and Grain? These three stream ciphers were chosen for the final hardware profile of the eSTREAM portfolio. As far as I understand it, their merits are:

Trivium: elegant design, very high throughput per area, small area, parallelizable.
Grain: simple design, small area, high throughput, comes in a 128 bits flavor and in an authenticated version, easy area-throughput tradeoff.
MICKEY: small area.

(source: http://asic.ethz.ch/estream)

As I see it, Trivium and Grain have many more strengths than MICKEY. So my question is:

Are there qualitative (e.g. a property like Trivium's parallelazibility) or quantitative reasons that would make MICKEY a better choice than the two other ones in some situations?

MICKEY appears to be a good low-power stream cipher but, in the context of the eSTREAM portfolio, it does not seem to excel at anything in particular. Trivium and Grain have more implementation flexibility and lower area, if one wishes, and Trivium also allows for fast bitsliced software implementations that rival the software eSTREAM candidates in speed.

The one thing MICKEY appears to be better at than others is simplicity (in number of VHDL code lines), as seen in Table 8 of Chapter 19 of the eSTREAM book. This does not strike me as a particularly strong argument for it, since the line numbers between the best entries are all fairly close together.

MICKEY also appears more conservative when it comes to security; in particular, Trivium and Grain have been targets of more algebraic-type cryptanalysis. But this is something that is hard to quantify, and may be mainly a consequence of Trivium/Grain being more popular than MICKEY.


Understanding an encryption technique algorithm I have trouble understanding steps for Key set generation mentioned in an article titled as "An optimized encryption technique using an arbitrary matrix with probabilistic encryption". The steps are:

Consider the sequence for 0 to n-1 values for a source text of size n = pow (p, p) characters.
Convert each element of the sequence into a form with base p.
Represent the values of step 2 in a matrix form A of order n x p.
Subtract 1 from each element of A.
Consider a random matrix B of size p x p.
Multiply the matrix A with B to generate a result matrix R.
Substitute all positive integers of R with +1, negative integers to -1 and zero by 0 using a substitute function.
Increment each element of R by 1.
Convert each row of R, from the base p to decimal to generate the key sequence set.

I can't understand how this works. Can you explain these steps with an example? Or pseudocode?

To be honest, this paper looks like garbage. It refers to Base64 as an "encryption algorithm" in section 2.2. Figures 1 and 2 were
created by a moron. But anyway...

  Consider the sequence for 0 to n-1 values for a source text of size n = pow (p, p) characters.

If $p = 4$, then $n = p^p = 256$ and we'll be working with a block of 256 bytes. But for brevity, I'll consider the simpler case where $p = 3$ and restrict the cipher alphabet to the 26 letters of the alphabet plus the space character.

Presumably the pass phrase will have to be padded to the block size before applying this algorithm, but the paper doesn't describe how to do this. Let's assume we're starting with the 27-character keyphrase THIS IS MY SECRET KEYPHRASE.

  Convert each element of the sequence into a form with base p.

If ' '=000, 'A'=001, 'B'=002 and so on, up to 'Z'=222, we get the following:

202 022 100 201 000 100 201 000 111 221 000 201 012 010 200 012 202 000
102 012 221 121 022 200 001 201 012

  Represent the values of step 2 in a matrix form A of order n x p.

$$A = \begin{bmatrix}
2&0&2&0&2& \dots &0&0&1&1&1\\
2&2&1&0&0& \dots &0&2&0&0&0\\
1&0&2&0&1& \dots &0&1&0&1&2\\\end{bmatrix}$$

  Subtract 1 from each element of A.

$$A = \begin{bmatrix}
1&-1&1&-1&1& \dots &-1&-1&0&0&0\\
1&1&0&-1&-1& \dots &-1&1&-1&-1&-1\\
0&-1&1&-1&0& \dots &-1&0&-1&0&1\\\end{bmatrix}$$

  Consider a random matrix B of size p x p.

This is under-specified. But let's assume the elements of $B$ are all in the range from $0$ to $n-1$:

$$B = \begin{bmatrix}
21&16&5\\
15&23&8\\
3&10&10\\\end{bmatrix}$$

  Multiply the matrix A with B to generate a result matrix R.

$$R = B \times A = \begin{bmatrix}
37&-10&26&-42&5&\dots&-42&-5&-21&-16&-11\\
38&0&23&-46&-8&\dots&-46&8&-31&-23&-15\\
13&-3&13&-23&-7&\dots&-23&7&-20&-10&0\\\end{bmatrix}$$

  Substitute all positive integers of R with +1, negative integers to -1 and zero by 0 using a substitute function.

$$R = \begin{bmatrix}
1&-1&1&-1&1&\dots&-1&-1&-1&-1&-1\\
1&0&1&-1&-1&\dots&-1&1&-1&-1&-1\\
1&-1&1&-1&-1&\dots&-1&1&-1&-1&0\\\end{bmatrix}$$

Wait a minute; if $p > 3$, then isn't matrix $R$ going to consist mostly of ones? Maybe $B$ should also include negative values? Who knows?

  Increment each element of R by 1.

$$R = \begin{bmatrix}
2&0&2&0&2&\dots&0&0&0&0&0\\
2&1&2&0&0&\dots&0&2&0&0&0\\
2&0&2&0&0&\dots&0&2&0&0&1\\\end{bmatrix}$$

  Convert each row of R, from the base p to decimal to generate the key sequence set.

This can't be right. Although $p=3$ in this example, the elements of $R$ consist of the values 0, 1 and 2 for any value of $p$. However, according to the encryption algorithm discussed later in the paper, we're supposed to end up with a set of $n$ values. So I guess we just replace each group of $p$ elements in $R$ with the result of interpreting them as digits in base $p$:

$$K = \begin{bmatrix}
20&8&18&20&0&18&11&9&0\\
23&1&18&2&0&18&2&20&0\\
20&2&18&8&6&18&2&20&1\\\end{bmatrix}$$

When flattened into a string of characters from the cipher alphabet, this is the result:

THRT RKI WARB RBT TBRHFRBTA

I'll probably lose the will to live if I start wading through the encryption algorithm, so I'll stop here.


How to prove that a ciphertext is encrypting multiplication of two values? Zero-knowledge proofs with soundness, completness and zero-knowledge enable a prover to convince a verifier that a witness validates successfully a predicate without giving any information about the witness and without the verifier being able to extract the witness from the commitment C. Such kind of functionalities are useful in ecash,evoting,anonymous credentials, etc. In an abstract way the sender wants to convince a set of parties that he knows how to open the commitment and also that the commitment entails a message with specific properties.

So a Zero-Knowledge proof can be seen as an extension of a commitment scheme but without giving the opportunity ever to the receiver to open the commitment and with allowing the receiver to verify a statement-predicate.

If we work in a public key setting with DLP as the hardness assumption such as ElGamal then the sender without giving the key to the untrusted verifier can provide proofs of zero-knowledge that the encrypted values does contain a value that follows some properties, using Schnnor or Pedersen protocols as a building block.

However i am not aware of any kind of proofs that the encrypted value under some stream cipher for instance:$E(m)=m \oplus k=c$ for some random key k can be used to convince the verifier that c is the encrypted value of $m=a*b$ for some $a,b \in [0,range]$. Or more generally how i can prove that i have encrypted some specific values by giving the receiver only the ciphertext. Because it might be trivial that in a protocol you can prove a zero-knowledge of a value that you hold and you can use (for obtaining access anonymously to some credentials) but in most of the times this value is sent encrypted so there must be an association between the ciphertext that truly contains what is supposed to be known in the ZK proof and the ZK proof itself

Yes, this is doable.  You can verify that $m=a \times b$, given El Gamal encryptions of $m,a,b$, since El Gamal is multiplicatively homomorphic.  You can also prove that the El Gamal decryption of some ciphertext is in a given range (using a combination of Schnorr proofs).  Putting those two together will give your first desired primitive.

This requires you to use El Gamal encryption rather than a stream cipher.  However, if this is a problem, it is also possible to do it for other encryption schemes as well.  It is known that every statement in NP can be proven in zero knowledge using generic (but slow) schemes, so this can also be extended to work for any stream cipher.  The advantage of ZK proofs based upon El Gamal or other public-key schemes is that they can be made more efficient.

See, e.g.,

Proof of correctness of a homomorphic ElGamal sum
Is there a public key semantically secure cryptosystem for which one can prove in zero knowledge the equivalence of two plaintexts?
http://www.win.tue.nl/sedan/sedan2009/SchoenmakersSedan2009.pdf

There is tons written on this subject in the research literature.  You'll need to do more research on your own to learn this subject.  You should spend some days studying basic material on learning elementary zero knowledge proofs, first by reading textbooks, then by reading some of the classic papers.  A good starting point would be to look at textbooks on theoretical cryptography, such as
Rafael Pass and abhi shelat's lecture notes and Wenbo Mao's textbook.  You could also read http://www.austinmohr.com/work/files/zkp.pdf


How does a user register his verifier at host in SRP (Secure Remote Password) protocol? I read RFC 2945 and 5054 describing SRP, but there was no mention of registration.

How should user registration happen in SRP? Is there a standard or paper describing it?

As mentioned in the comments this is a standard problem not unique to SRP and not really about the cryptography of SRP. So this question would probably be better posted on 'security.stackexchange.com' as it is more of a generic problem.

Fundamentally setting a shared secret like a regular password or a password verifier over a public network has its challenges. For most applications the standard techniques used to reset a regular password can be reused in the setting of the password verifier.

The diagram on this page in the context of a javascript SRP library shows how the user is registered onto a websites secured using SRP. The user keys in the password into the browser and javascript generates the verifier and transmits it to the webserver. You don't want people to run an offline dictionary attack against the verifier so it is a form of shared secret. This means you want to protected it like you would protect them setting/registering/resetting a traditional password (e.g. use https and aes encrypt it within the database).

The only choices you have is whether the salt of the user is generated by the client or the server. It makes sense for the server to do this as it can ensure that the salt has high entropy and is unique to the user.


Breaking Double Encryption I am trying to understand how an attacker knows when he has successfully decrypted a ciphertext for an assignment. As such, some pointers/hints for the following questions would be greatly appreciated.

If you double encrypt secret data with two different algorithms. How does the attacker know if he already broke the 'first layer' of encryption?
Is it possible to determine the encryption algorithm used by analyzing the cipher text?
If you find out what algorithm was used does it give you the necessary information to know when you successfully broke the 'first layer'?
Considering the above, what difference would it make if the attacker knows the open-source program or the (public available) algorithms used to protect the data?

To begin with 4: Remember Kerckhoff's principle. You should always assume that the attacker knows which algorithm is used to encrypt your data. All the algorithms used in practice are designed to be secure under this assumption, so you should consider that hiding the algorithm from the attacker is superfluous. But as a hypothetical...

I can't think of any real-world cryptosystem where it would be possible to tell exactly which algorithm was used knowing only the ciphertext, but in a theoretical sense such an algorithm could exist, and would not be any less secure because the attacker is supposed to know that anyway.
Same as above, for mostly the same reasons.
In light of the above, it shouldn't make a significant difference. If it does, your algorithm relies on security by obscurity, and is generally worthless.

In your "double encryption" case, the attacker will just treat the composition of the two algorithms as one big algorithm, he will not try to decipher one and then the other.


How hard is it to guess a 8 digit PIN? Say that there are different live situations where you have to select own PIN numbers.

Can someone say if it is possible to guess a 8 digit pin within 3 tries, given any methods or resources?

Is this too hard with today's technologies or possible? What about quantum computing?

And if you know, could you tell me the entropy for this case?

If a computer is doing the selection of PIN numbers, then you would be very lucky indeed to guess a PIN in three times. The entropy - assuming that all numbers are valid - is of course $\log_2{10^8} \approx 26.57$ bits.

The chances of guessing the PIN correctly in 3 tries is $$1 - \frac{x-1}{x} \cdot \frac{x - 2}{x-1} \cdot \frac{x-3}{x-2} = 1 - \frac{x-3}{x} = \frac{x}{x} - \frac{x-3}{x} = \frac{x}{x} + \frac{-x+3}{x} = \frac{3}{x}$$ where $x$ is $10^8$, so $3\times 10^{-8}$ or just $0.00000003$. This is basic math (which I managed to get wrong quite a few times, thanks to Max O. for correcting me the last time around).

Once you have a limited number of tries, the different technologies make no difference anymore. Quantum computing will allow faster computations, but since you only get 3 tries, speedup is not of any interest.

If a user creates a PIN then PIN numbers such as 00000000 are  very likely, and your chances depend very much on the person choosing the PIN. Some banks will therefore disallow the exceptionally stupid ones, leaving just the normally stupid ones. Even smart persons have been shown to be terribly bad at generating random numbers. How bad they are is hard to know, it very much depends on the target audience, I presume.


Is it safe to use RSA as a proof-of-work system? Suppose I devised the following challenge-response proof-of-work system:

A server generates a 2048-bit RSA modulus, and uses the "public" exponent (usually 65537) to sign a random nonce a fixed number of times, say, 256.

The server then sends the signed nonce to the client, along with the "private" exponent (which is much larger) and modulus, asking it to un-sign it using the private key 256 times, sending the answer back for the server to verify. Because the private operation takes about 300 times longer at 2048 bits, the client will take longer to un-sign the key than the server took to sign it.

Is this usable/secure? Or does the generation of the modulus outweigh any gains in the difference in signing time? If so, how could I make it usable, if at all?

Is this usable? Or does the generation of the modulus outweigh any
  gains in the difference in signing time?

No, it does not work. The generation cost itself isn't too important, because signing any one nonce doesn't help the client sign any other nonce, so you can just use a single key all the time (if you had to create a new keypair for every puzzle, this would be very impractical and nobody would use it).

But the problem is that the advantage of the server on the client is asymptotically more or less zero, so this is quite useless as a proof of work scheme. See D.W.'s answer for one way of breaking the scheme.

Another way similar to D.W.'s is to realize that your scheme requires the client to compute, given a random  nonce $a$ and a work factor $k$, modulus $n$ and private exponent $d$:

$$\text{proof} = ((a^d)^d)^{\cdots ~ k ~ \text{times}} ~ \text{mod} ~ n$$

And this is equal to:

$$\text{proof} = a^{d^k} ~ \text{mod} ~ n$$

But because the client knows $d$ (you gave it to him!) he can factorize $n$ in constant time and compute $\varphi{(n)} = (p - 1)(q - 1)$, which gives him the ability to reduce the inner exponent:

$$\text{proof} = a^{d^k ~ \text{mod} ~ \varphi{(n)} } ~ \text{mod} ~ n$$

The client can calculate this in $\log{k}$ modular multiplications or squarings by $d$, and $\log{n}$ (on average) modular multiplications or squarings by $a$. But the server has to do pretty much the same amount of work - the only difference is it saves some time because $e$ is smaller than $d$. The gain is minimal and very difficult to control, since there's a point where you just can't make $e$ any smaller and need to increase $n$ to compensate.

In conclusion, this is not a good proof-of-work scheme, as it provides basically no control over the work factor desired and the server will need to work about just as much as the client for realistic values of $n$ and $k$.

  If so, how could I make it usable, if at all?

However, it's possible to take your scheme a step further to make it cleaner (and not depend on RSA). The idea is to choose a "difficulty factor" $t$, a random number $a$, a large $n = pq$, and ask the client to compute:

$$\text{proof} = a^{2^t} ~ \text{mod} ~ n$$

The client will require $t$ squarings to achieve this (there is no known way to do better, and it cannot be parallelized to any significant degree), while the server, knowing the factorization of $n$ (since it generated it) can just compute:

$$e = 2^t ~ \text{mod} ~ \varphi{(n)}$$

And hence, from Euler's Theorem:

$$\text{proof} = a^e ~ \text{mod} ~ n$$

Which the server can then compute in logarithmic time. In effect, the server only needs $O(\log{nt})$ time, but the client needs $O(t)$ time. By making $t$ arbitrarily large, you can fine-tune the amount of work you want the client to do, linearly, but the work stays logarithmic for the server, which is practical.

The generation cost is also irrelevant, because the server can generate it once and reuse it all the time with different values of $a$ (that's not always true, but in this case it is - the attacker can't use the results of a previous proof of work to quickly solve another assuming $a$ is random and $n$ is large).

Note your scheme doesn't care if the client can factorize $n$ since you are basically giving away $d$, but in this scheme it is imperative that $n$ be large enough so that factorization is not possible. But this is easy to address, just create a 2048-bit modulus (or 4096-bit if you are paranoid) and be done with it.

For more details and supporting theory on this method, see:

Time-lock puzzles and timed-release Crypto, Ron Rivest, Adi Shamir, David Wagner.

Puzzle description for the MIT time capsule.


Stream cipher - Many time pad I understand the concept that when you xor the cipher texts you get the XOR messages cause the keys get XOR-ed and cancel out... This is at least the case when both the messages are of equal lengths.

What about when both the messages are of different lengths? Does the shorter message get padded? Which of the key would be of the original length key (non-padded)?

No usually the shorter message doesn't get padded, you can just not decrypt or at least analyse the last part of the longer message. If the key is not even the same size as the message then you are dealing with a variation of the Vigenere cipher, not with a one-time-pad.

What happens in practice is of course dependent on the situation. But if the key is reused of an OTP then the security is lost, and usually in a rather catastrophic way.


can I use PBKDF2 instead of hmac as a hashing tool for sensitive data I have read about hmac and PBKDF2.

PBKDF2 - is mainly used for password hashing. It uses hmac and iterates.

I want to hash some sensitive data and send in the response of a request.

Later that hashed sensitive data will be send back with some form data.

So in my case is it safe to use PBKDF2 as hashing tool - to hash any thing like (timestamp+sensitive_info+extra_info) with a SECRET_KEY just similar to hmac

So in my case is it safe to use PBKDF2 as hashing tool - to hash any thing like (timestamp+sensitive_info+extra_info) with a SECRET_KEY just similar to hmac?

The reason that a Password Based Key Derivation Function or password hash is used is because passwords are generally not considered secure enough. The iterations or work factor of such a PBKDF makes it harder for attackers to use dictionary attacks and the like to retrieve the password value and any derived key from it.

However, if you already have a secure secret key then there is no need to perform PBKDF2. It doesn't depend on the sensitivity of the protected data at all. So if you have a secret key and you just need integrity and authenticity, then you can just use a normal MAC - such as HMAC. If you also need confidentiality then an authenticated cipher such as GCM makes more sense.

Beware that HMAC doesn't have a salt; you may need a nonce or IV value to make your message / ciphertext secure (but this depends on the threat model for your particular use case). If you use a timestamp then this may be part of providing message uniqueness (although timing information is always a bit dangerous due to precision and reset issues).


How to generate a public key from a private ECDSA key? Having some specific ECDSA curve and a private key, how does one calculate the public key? I am having a hard time finding the algorithm and equations for it.

The write up on Wikipedia is pretty good. I won't go into all the detail that they do there, but your private key is a randomly selected integer $d_A$ selected from $[1,n-1]$ where $n$ is the order of the group. The public key is $Q_A=d_AG$ where $G$ is the base point on the curve defined in the publicly agreed upon parameters.


Does this use of hash provide anything over a nonce? HMAC instead? I ran across some CSRF code that does:

Tokens.prototype._tokenize = function tokenize (secret, salt) {
  return salt + '-' + hash(salt + '-' + secret)
}

where hash seems to be a SHA1 digest modified to fit in a multipart/form-data body without extra encoding:

function hash (str) {
  return crypto
    .createHash('sha1')
    .update(str, 'ascii')
    .digest('base64')
    .replace(PLUS_GLOBAL_REGEXP, '-')
    .replace(SLASH_GLOBAL_REGEXP, '_')
    .replace(EQUAL_GLOBAL_REGEXP, '')
}

IIUC, the use of hash doesn't prevent forging.
Does this provide much over just using a closely held nonce?

Does hash make it particularly difficult to derive the input?  Since secret is not encrypted, this seems to assume that either

secret need not be secret or
the token is closely held, which should be the case for a CSRF token.

the use of hash doesn't prevent forging. Does this provide much over just using a closely held nonce?

on the contrary, the use of hash described should prevent forging assuming the secret is kept .. well.. secret

  Does hash make it particularly difficult to derive the input? Since secret is not encrypted, this seems to assume that either

Indeed, it should be very hard to derive input (secret) from its hash. That's one of the mandatory properties of a hash function. The secret should stay secret on the server side (not revealed to the client)

  secret need not be secret or the token is closely held, which should be the case for a CSRF token.

if the secret is revealed, the client could forge a new valid CSRF token


How does the certificate authority generate a signature F? E=encrypt(K,M) - is message M encrypted with key K gives encrypted text E

M=decrypt(K,E) - is encrypted text E decrypted with key K gives message M

KCA−pub,KCA−priv - is the private-public key pair for a certificate authority, such as Verisign

D=MD(F) - MD is a message digest function, applied to file F giving digest D

F - is a file containing Bob’s public key, KBob−pub, and email address, EmailBob

How does the certificate authority, CA, generate a signature S from the file F using the functions above, in order to build a certificate for Bob consisting of file F followed by the signature, S?

this is my answer:
Firstly, Bob will need to go to a well-known authority (such as Verisign) to prove who he is using a passport or driving license or something to prove it is him. A public-private key is generated paying a fee and receives a certificate consisting of his public key and a statement of his identity (such as name, email, address etc.) all hashed and signed with the private key of the authenticating company.

Anyone can verify his public key belongs to him by comparing it with the signature decoded with the public key of the authenticator.

Signature
Encrypt - ED = encrypt (Kca-pub-bob, MD(F)

Decrypt - MD(F) = decrypt (Kca-private-bob, ED)

As far as I understand the question, you ask how a (client-)certificate is issued and generated.

Normally this works like this:

Get an account at the page of the CA. (this is important in later steps)
Validate your identity against the CA, f.ex. using documents like driver-license or passport. Your account will then be listed as "verified as owned by XYZ"
Then you'll create a CSR (certificate-signing-request). This is basically an unsigned X.509 certificate, containing all relevant data about you (=name and your public key)
You send the CSR over to the CA. They will check the your signature on  the CSR to make sure you own the private key associated with the public key. They will also validate that the data in the CSR matches with the data they verified about you.
Now they know that this request is valid. So they'll form a X.509 certificate by taking your CSR and adding their data (where to get CRLs from, validility period, the CA-data,...). Now the certificate is signed by them and the certificate is send back to you. The hash is not stored (as far as I know) and just an intermediate value.

As a formula this would look like this: $Cert=F||S_{CA}(SHA256(F))$.
Where $S_{CA}(X)$ means the signature of the CA on X.

I hope this answers your question. If not use the comments or edit the question.


What is Indistinguishability Obfuscation? I've been studying functional encryption. I recently read that a multi-input functional encryption (MIFE) implies indistinguishability obfuscation (IO).
Can someone please brief me: what is indistinguishability obfuscation (IO), and are its implications for crypto?

Program Obfuscation is a method to scramble the program code such that it becomes unintelligible but preserves the program's functionality. The notion of indistinguishability obfuscation was proposed in [BGI+01]. Actually they first consider another notion which is called virtual black box obfuscation (VBB Obfuscation). However, they showed that VBB Obfuscation is impossible, so they proposed the concept of indistinguishability obfuscation (IO).

In 2013, [GGH+13] proposed the first candidate IO from assumptions over multilinear maps. After that, a number of its applications were proposed. For example, deniable encryption [SW14], witness encryption [GGSW13] and round optimal (2-round) MPC [GGSR13] (Actually, just review the list of IACR preprint after the appearance of the first candidate IO, you could find a great number of paper discussing applications of IO).

Currently the central problem is how to build IO from standard mathematical assumptions (e.g., LWE and Bilinear Maps). The most most recent breakthrough was made by Rachel Lin et.al. from last year through this year [Lin16][LV16][Lin16][AS16][LT17].


RSA: Know the public key from a pair of plain text and their cipher? I have two plain texts files cipher with RSA (with the same public and private key) and I have their cipher texts too. Would it be possible know the public key from that information?

My messages have 10 characters and I cannot calculate a huge exponential operation. No padding is used on the messages before encryption.

From a couple of plaintext/ciphertext $(m_1, c_1)$ and $(m_2, c_2)$, then the modulus $n$ is a factor of
$$
\gcd(m_1^e-c_1, m_2^e-c_2).
$$
The explanation is that
$$
c_i = m_i^e - \lambda_i n
$$
for some unknown $\lambda_i$, so $n$ both divides $m_1^e-c_1$ and $m_2^e-c_2$.

Of course, this solution works if you know $e$, but it can be tried with some classically used values ($e=3$ for instance).


Blind signature with openssl I'm trying to understand (to reproduce in practice) how does blinded tokens work. Currently i'm lacking examples. According to Wiki the blinded signature protocol is the same as ordinary signature protocol. So maybe it is possible to reproduce it with the help of openssl? I want to reproduce by hand all the steps required to sign

Blind signatures can be constructed from a ordinary "textbook" RSA signature by seperating the blinding/unblinding operations from the signature operation. The problem is that we do not use textbook RSA signatures in practice. Rather RSA signatures are padded, which increases the security of the signature but also destroys the ability for blinding.

Some libraries, OpenSSL included, do allow you to do a "raw" RSA signature. The Wikipedia article contains how to do a blind signature with RSA –– I'm not sure how much I can add. Essentially, you choose a random integer $r$, raise it to the power of the public key (integer) $e$ mod integer $N$, and multiply it (mod $N$) by the message you want signed. Instead of submitting the message itself to the signature algorithm, you submit the result of multiplying it by $r^e$. The signtuare algorithm will return a signature $s$. Multiply s by $r^{-1}$ and this will be a valid RSA signature on your message.


Are HMACs based on hashes with larger bit-lengths also more secure? When doing encrypt-then-mac, I can choose to use a hmac as the MAC. For example, I could use a hash like SHA-256 or SHA-512 (by using it as a keyed hash) to create that HMAC.

Does it increase security when choosing a hash with a larger bit-size? Is a HMAC based on SHA-256 weaker than a SHA-512, or doesn’t it really matter because both are cryptographically secure?

HMAC-SHA-256 is sufficient for up to 256 bit security. Confer e.g. NIST SP 800-107. This recommendation is based on the premise that collision attacks are infeasible against common uses of HMAC, and that you consequently only have to worry about primary pre-image attacks that attempt to recover the secret key (and use this for forging subsequent messages).

SHA-256 has 256 bit security against primary pre-image attacks. This is sufficient for all practical purposes.


Can homomorphic decryption of DES be practical? I was reading this paper Homomorphic evaluation of the AES Circuit by Gentry et al. when I thought if something similar can be done with DES or 3DES, e.g. it is plausible to decrypt DES homomorphically ?

Every algorithm that can be modeled as a Boolean circuit can be homomorphically encrypted. DES/3DES can surely be modeled by a Boolean circuit.

The question is if it is practical to use DES/3DES for homomorphic encryption. I don't think so.


Can you help me understand how RC4-52 is done using pen-and-paper? I've played a lot with VIC and enjoy its complexity and effectiveness as a field cipher. However, RC4 has caught my attention lately and I've read there is a RC4-52 variant that can be done by hand.

Can anybody describe the rc4-52 algorithm? Is it with a deck of cards and just a swap of the values, or must they still be added somehow?

You can do RC4 using a 52-entry table, instead of a 256-entry table.  All you do is change the modulo-256 arithmetic in RC4 to use modulo-52 arithmetic.  There are no special changes needed, and no need to describe a special algorithm.  If you want to see a  description of how to perform it manually using a deck of cards, you can find that here:  http://www.mail-archive.com/cryptography@wasabisystems.com/msg00065.html  See also https://groups.google.com/forum/?fromgroups#!topic/sci.crypt/dw3FaK4lf2M

Related: If you've read Neal Stephenson's Cryptonomicon, you may have seen a reference to an encryption algorithm that can also be carried out with a deck of cards.  The cipher is called Solitaire.  It was invented by Bruce Schneier and was apparently inspired by RC4.  However, it has cryptanalytic weaknesses.  (If you haven't read Cryptonomicon, and you like science fiction, check it out: you're in for a treat!)

Keep in mind this is entirely theoretical.  Performing RC4-52 with a deck of cards will be extremely slow and tedious in practice.  And while I don't know of anyone who has seriously studied its security, there are reasons to doubt whether it will be secure against a serious attack.  While it's fun to contemplate, I would not recommend that anyone use this to protect real secrets.