Anatomy of an RSA private key I'm learning about OpenSSL and public key infrastructure and am curious about the structure of an RSA key and how it's related to its corresponding public key.

I can generate a private RSA key with the OpenSSL genrsa command:

$ openssl genrsa -aes128 -out fd.key 2048
Generating RSA private key, 2048 bit long modulus
....+++
......................................................................................
+++
e is 65537 (0x10001)
Enter pass phrase for fd.key: ****************
Verifying - Enter pass phrase for fd.key: ****************

I know there are three factors to think about when generating a private key:

Algorithm
Size
Passphrase

In this case, I'm using the RSA algorithm, 2048 bit size, and encrypting the key with AES-128 encryption.

I can view the structure of the RSA key using the rsa command:

$ openssl rsa -text -in fd.key
Enter pass phrase for fd.key: ****************
Private-Key: (2048 bit)
modulus:
    00:b6:ae:03:fa:d5:ec:3d:7b:1e:a5:33:68:44:5f:
    [...]
publicExponent: 65537 (0x10001)
privateExponent:
    1a:12:ee:41:3c:6a:84:14:3b:be:42:bf:57:8f:dc:
    [...]
prime1:
    00:c9:7e:82:e4:74:69:20:ab:80:15:99:7d:5e:49:
    [...]
prime2:
    00:c9:2c:30:95:3e:cc:a4:07:88:33:32:a5:b1:d7:
    [...]
exponent1:
    68:f4:5e:07:d3:df:42:a6:32:84:8d:bb:f0:d6:36:
    [...]
exponent2:
    5e:b8:00:b3:f4:9a:93:cc:bc:13:27:10:9e:f8:7e:
    [...]
coefficient:
    34:28:cf:72:e5:3f:52:b2:dd:44:56:84:ac:19:00:
    [...]
writing RSA key
-----BEGIN RSA PRIVATE KEY-----
[...]
-----END RSA PRIVATE KEY-----

I'm also able to view the public key using the using the rsa command:

$ openssl rsa -in fd.key -pubout
Enter pass phrase for fd.key: ****************
writing RSA key
-----BEGIN PUBLIC KEY-----
MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEAyOYm8hJCi3vKLaud2YTU
O3glFfQUpJ6d4gXiWp//HkDQIvi2BFmvbUyHMh4XWLwPbmaX2dfJ5Aa8+ZIC9KCY
y96Gmbw+v75RzxHq5iFLnZNFhYM2zkMvUUjJs/UqunOL1OoEiC06hb85SBepKtnE
JUUKo/rtZ2Sj/pHvF0Wqu1hLyR3iOxdJb26+m2IhOy4wB3HI6FBcvrMd4Hmejpup
skIRhTQXkV7XQ79yRCTS3ejiGoVvkPKzWxL+OFWOJTduXAk8McMLEozSGZll8bv7
jJUWLhmegvokKS2eLfA4B16yU59EgNbvuoG5doKUeV0LJ03Iiqv81nFB9SqEG/Xe
VQIDAQAB
-----END PUBLIC KEY-----

From the Hexadecimal wiki page:

  One hexadecimal digit represents a nibble (4 bits), which is half of an octet or byte (8 bits).

Some things I'm curious about:

Which numbers correspond to the 2048bit length? Is it prime, exponent, coefficient...?
How is the public key related to the private key? Is it calculated from the numbers, or is it embedded in the private key?

From reading another answer it sounds like the 2048 length corresponds to the modulus.

However when I calculate the length I get 2056:

$ echo "00:b6:ae:03:fa:d5:ec:3d:7b:1e:a5:33:68:44:5f:d0:6a:0b:b5:87:31:80:a0:50:32:b0:7c:73:4b:f8:a2:03:91:89:c2:11:32:69:2e:13:90:71:f6:a9:48:21:00:c5:ad:1c:93:f0:21:27:ce:ca:15:04:53:30:c6:88:7b:45:c0:f2:01:d5:a7:9e:c1:c5:f2:ae:b0:7f:31:68:b7:3c:c3:62:13:eb:40:25:a9:3f:cd:81:90:9f:a1:3f:02:84:d8:6e:73:d2:5d:53:28:cc:97:35:f6:fa:5c:b7:dc:11:fb:60:08:1b:75:f7:74:dc:24:29:3e:ff:fb:ba:dc:77:2c:48:0d:3b:a1:7b:d9:9a:3d:52:7d:9a:d6:c1:f1:e7:46:df:be:75:b0:d2:0f:d2:1c:7b:25:57:94:33:8f:d5:b3:ee:7f:30:98:a9:06:25:b5:ab:b1:a6:ab:f9:f2:52:b8:e7:8f:87:5f:6d:96:36:67:47:38:4c:ef:29:c7:71:e4:07:7c:13:19:3a:e2:b4:3c:85:18:32:77:a6:98:0e:0d:b4:70:01:75:79:de:e9:83:c5:df:41:2f:69:f6:30:8d:13:29:84:9a:84:3a:c0:6a:4c:0d:bd:cd:9b:1e:93:de:8e:c9:a4:02:b7:0f:a2:96:45:ad:b8:3e:3a:d3:fd:4d" | tr ':' '\n' | wc -l
257

Each line contains 2 hexadecimal digits

257 * 2 = 514

Each digit contains 4 bits

514 * 4 = 2056

Shouldn't it add up to 2048?

Which numbers correspond to the 2048bit length? Is it prime, exponent, coefficient...?

Only the modulus really - the key size is identical to the modulus size by definition. The primes are commonly half of the key size for calculations that use 2 primes (multi-prime RSA is faster and on the uptake). The private exponent may not reach the full key size; it's between 0 and the modulus (exclusive). There is a high chance that the size is the same or slightly less than the modulus in bytes.

  How is the public key related to the private key? Is it calculated from the numbers, or is it embedded in the private key?

It's calculated during the key pair generation process - the output of which is both a private key and a public key. The private key and public key share the same modulus. Often the private key - generated by a specific tool such as OpenSSL - contains the public exponent, so you can also extract / use the public key if you have the private key.

Usually the public exponent is a known, small value - such as the fourth prime of Fermat: 0x010001. But as that may not be the case the public exponent (and thus the public key) in general isn't calculated from the private key components. If the public exponent is the same size as the private exponent then you cannot calculate it from the private key values.

  From reading another answer it sounds like the 2048 length corresponds to the modulus.
  However when I calculate the length I get 2056 ...

ASN.1 / DER encoded INTEGER values are signed, big endian. As the most significant bit of the positive modulus is always set - assuming that the key size is dividable by 8 - it will always left-pad the modulus with a padding byte set to 00. Otherwise the encoding would represent a negative value in so-called two-complement encoding - the most significant bit is seen as the sign bit: 0 for positive number representation and 1 for negative number representation.

So the signed encoding in octets of the modulus is 2048 + 8 bits or 257 bytes. But the bit length - as it is called in most programming API's - of the modulus is still 2048.

Note that OpenSSL shows the generation parameters required to use the Chinese Remainder Theorem to speed up RSA calculations. In principle a private key could also consist of just the private exponent and the modulus.


Why is it secure to reuse key and nonce in ChaCha20-Poly1305 AEAD construction? While looking at the ChaCha20 and Poly1305 AEAD construction as defined by RFC 8439, more precisely its use of the key and the nonce, I came up with the questions below. Maybe someone with some in-depth knowledge is willing to share it?

The key and the nonce (usually a "number to be used only once") are used twice in this construction: first, to generate the Poly1305 one-time key using the ChaCha20 block function, and second, to encrypt the plaintext using the ChaCha20 function. Why is this reasonable and secure? Especially as both are using a related construction and its stated for ChaCha20 that the nonce "MUST not be repeated for the same key".
In the AEAD construction, the nonce is not explicitly authenticated by the MAC. Is it still secure to include the nonce in the AAD as this could be treated (at least in some way) as a reuse of the nonce with the same key? I guess it is secure, but can someone explain why this is so?

Actually, by your own criterion, the same nonce is routinely used much more than twice, because each call to the ChaCha20 core function reuses the same key and nonce, except with a different counter value.

Here's the problem that's tripping you up: the prohibition on using the same key/nonce pair to encrypt more than one message applies to the construction's callers, not the construction's internals. The implied tension you're reading between the external requirement and the internal details just isn't real.

But, internally, the fact that each call to the core function within an invidual encryption operation uses a different counter value is relevant here.


What should the size of the private exponents in Diffie-Hellman key exchange for TLS be? I'm using TLS with a Diffie-Hellman key exchange to negotiate the symmetric keys.
How long should the exponents be?

Diffie-Hellman exponents need at a size at least twice the security level.

So for elliptic curve DH you need the same size as the underlying field. For example 256 bits for P-256.

For finite-field DH you still need twice the security level as exponent, but significantly larger fields. For example for an 80 bit level you need 160 bit exponents and a ~1024 bit field.


How does this SSL-related flaw work? I just saw a video at CNN in which it is claimed that, if the server isn't generating a random public key, the server can be hacked.

First how HTTPS works… to be sure I’m on the same page:

Server has a public key and a private key. Client uses the public key to encrypt data before sending it to the server. Then the server uses its private key to decrypt that data… which is the only way to decrypt it.
Client makes sure – using an SSL service provider – that the public key the server is offering is indeed genuine and belongs to that server. Otherwise, if someone “in-the-middle” would change the key, then that someone (via a fake server) would be able to read the data instead of the actual server.

Questions:

Does a server that offers HTTPS have to update its public key for every request it gets? Or is it true that – usually – it doesn't and therefore the claimed flaw exists?
How is the man in the video able to get the password? How is he able decrypt without using the private key?

If my understanding of SSL is bad, so it would be nice if you could explain this flaw to me.

Assuming this is "usual" HTTPS using SSL/TLS with RSA key exchange, the client generates a random secret, encrypts it with RSA (using the server's public key) and sends it to the server. The server then decrypts it (using its private key), and both generate from this (now shared) secret (and some public data depending on the messages) several keys which are used for encryption and MAC in both directions.
Then the actual HTTP message is sent encrypted using the exchanged key.

The video is not really clear in how the "hacker" breaks the encryption.

Here are two possibilities how bad random numbers might do this:

The server generated its RSA key pair using bad randomness, and the hacker succeeded to guess these random numbers, and thus arrive at the same key pair. Of course, then a simple packet sniffer can decrypt the message with the RSA-encrypted secret, and from this calculate the session keys.
The client generated its "secret" (which would be sent to the server) using bad randomness. The hacker guessed this secret (verified the guess by RSA-encrypting it using the public key), and then could derive the same session keys as client and server.

Note that using a Diffie-Hellman-based key exchange would prevent at least the first attack, assuming the ephemeral public DH-key has enough entropy to prevent brute-forcing it during the attack.

Using a different RSA public key for each session (or at least rotating every some time) might also help, but requires that there is a master key available to sign it (i.e. have a CA on the server or nearby), and also needs enough entropy to actually help. (And if the master key has not enough entropy, still a MitM can break this.)

I can imagine some other (non-crypto) ways how this video could be created:

The "hacker" might be the owner of the server, and thus knows everything sent to it.
The "hacker" is the owner of the notebook, and thus can see everything sent from it.
The "hacker" configured the notebook to use some proxy, and to trust the certificate of the proxy. The proxy then can log everything.

These don't relate to any random number problem.


Which MACs can be converted into a secure unkeyed hash function? It is known that setting the secret key to a fixed, public value does not make MACs like CBC-MAC or GMAC  into secure unkeyed cryptographic hash functions that could be used - for instance - for digital signatures.

In other words, the resulting hash function is not 1st pre-image, 2nd pre-image, and collision resistant.

What are the MACs that do not suffer from that limitation? I believe HMAC is one of them, provided the underlying unkeyed hash is strong.

Are there any others?

EDIT: if the hash used for HMAC is broken, also the HMAC constructed with it will probably be so.

I have ask as part of my answer, "What problem are you trying to solve?"

Do you want a secure unkeyed hash function? If you do, then there are plenty of them around. Even some of the ones that are broken for some uses might be okay for yours (SHA-1 springs to mind -- note the discussion above on HMAC and how broken a hash function has to be). But really, you ought to look at SHA-256, SHA-512, or the new SHA-512/t construction.

If you don't like that, look at any of the SHA-3 finalists. (Full disclosure, I'm the co-author of Skein.)

You're right that HMAC is one of them -- but that's basically the null statement. HMAC is a wrapper around an unkeyed hash function that strengthens it against a number of attacks (and adds a key). If you remove the key (or make it a constant), then all you have is a function with two iterations of a hash function with a bunch of frosting and sprinkles over it. It is obvious that if you start with a secure hash function, make a secure MAC and then remove the key then that you will end up with a secure hash function.

What are you really asking? What do you really want to do?

Jon


Why does side-channel security focus on “shielding” rather than “jamming”? I have always found it weird when in a crypto discussion people stressed the importance of making algorithms runtime-deterministic, to the point of avoiding any compiler optimisations.
To me, it seems that it's from the start futile to try and completely avoid side-channel information leaking out. Even if an algorithm always takes the same number of processor cycles: the processor is ultimately a coupled bunch of wires, and any signal passing through anywhere will inevitably couple to output connectors in the form of clock jitter, power-supply sag, etc.
The real question seems to be not whether information leaks out but whether the secret pieces of information will be possible to reconstruct. Granted, minimising leakage does always make this more difficult, but it is only one factor. In isolation, even a very small signal can be analysed.
Physically speaking, the crucial quantity is the signal-to-noise ratio: if a little bit of signal comes out on a given channel but also a whole lot of random noise, and you have no a-priori way of telling them apart, then extraction of the secret becomes exponentially inefficient.
In particular, for timing attacks, I think it would be a much better approach to not try and make the timing completely deterministic, but instead to make it deliberately completely nondeterministic. The simplest way would be to let the processor randomly intersperse the crypto calculation with nonsense boilerplate instructions (ideally, triggered right at the hardware level with a shot-noise source). The attacks I've read about seem rather delicate and would fail even if only part of the attacker's timings were foiled.
More sophisticated schemes might instead randomise the order of instructions or quickly multitask between many unrelated computations.
All such methods would incur some performance penalty, but it would likely be offset if we were again able to optimise our code without reservations. And we would be safer than with the approach of trying to eliminate any side-channels from forming in the first place. Processors are so complex that there will always be side-channels that weren't discovered, but the outside connections are better to oversee. If, without exception, all connections to the outside are thoroughly jammed, it doesn't matter what side-channels are open inside because only the public signal is strong enough to stand out over the noise floor.
What am I missing? Are these just my thoughts as a physicist and inapplicable to cryptography for some reason?

Physically speaking, the crucial quantity is the signal to noise ratio: if a little bit of signal comes out on a given channel but also a whole lot of random noise, and you have no a-priori way of telling them apart, then extraction of the secret becomes exponentially inefficient.

Actually, it becomes quadratically inefficient.

For example, if you have a signal to noise ratio of 1::1000 (1000 times more noise than signal), then it takes approximately $1000^2 = 1000000$ samples to extract the noise.

Given that:

1000 times more noise than signal is quite a lot
1,000,000 samples is quite doable in some scenarios
The implementer would have to be quite careful to make sure that the signal cannot be extracted from the noise in some simple manner

That this approach is generally seen as mostly unworkable (and doesn't immediately address cache-based side channels).

In contrast, just designing the code to be constant time/memory access is, for the majority of primitives we're interested in, isn't that infeasible, and so that's the direction we tend to go.

In contrast, you appear to also be worrying about DPA style attacks, where the attack listens into the electronics (power draw, emitted EMF, etc).  Well, we can't actually design gates that literally don't change power dissipation and don't generate EMF while switching, and so in that scenario, the strategy changes.  When we do worry about that, the typical strategy is to include randomness, but not randomly (as you appear to be suggesting); adding randomness randomly would leave open the question of whether there is some nontrivial correlation present.  Instead, we either:

Use some mathematical property of the primitive we're using that allows us to include randomness without modifying the answer.  As a simple example, to do modexp (where the exponent is secret) over a prime modulus, we may rely on:

$$A^B \bmod P = A^{B+R(P-1)} \bmod P$$

where $R$ is a random value we pick for this computation.

Use threshold logic; where each logical bit of the computation is expressed as a function (often XOR) of $N$ physical bits, and each physical bit (actually, each set of $N-1$ physical bits) is uncorrelated to the logic bit; we use randomness to translate each logical bit into the actual set of physical bits to represent it.

The first strategy is often used for public key cryptosystems (which often have the internal symmetries we need); the second is usually used for symmetric systems (this strategy is significantly more expensive, however we don't have a cheaper alternative)


How do you get $d$ in textbook RSA So people say to choose $d$ such that $e*d=1(mod((p-1)*(q-1)))$.

However, $1\%$ anything always equals $1$. Maybe I am not understanding it correctly, but the only way to get $e \cdot d=1$ is just by doing $e^{-1}$ which leads into a very very small number $\lll 1$ because $e$ is large.

How are people getting $e$ and $d$ such that they are both large numbers?

My main confusion really just comes from that $1\%$ anything always equals $1$.

There are no percentages, fractions, real or floating point numbers involved.

When using modular arithmetic, the "division" operation is defined differently. If you have some values $a, b$ that have been multiplied together into $ab$, what you want from division is that $\frac{ab}{b} = a$, or stated alternatively that $\frac{a}{a} = 1$.

When working with modular arithmetic, you need a different division operation than the "normal" one taught in basic math classes. This is easy to see with an example. Suppose that you have $$a=5\\b=7\\N=19\\ab \equiv 16 \bmod N$$ It is easy to see that dividing (in the traditional sense) $16$ by $7$ is not going to yield $5$.

Instead, you can multiply $16$ by $11$, which happens to be equivalent to $5$ modulo $19$. This fulfills the behavior expected of the division operation, which is what we really care about.

A value $\frac{1}{b}$ such that $\frac{ab}{b} \equiv a \bmod N$ is called a modular multiplicative inverse.

Back to the specific question

In the case of RSA, $e$ and $d$ are modular multiplicative inverses: $ed \equiv 1 \bmod \lambda(N)$.

Alternatively, you can denote $d$ by $\frac{1}{e}$ or $e^{-1}$; These are different ways of writing the same value.

A multiplicative inverse exists if the element is coprime to the modulus $N$. To actually find a modular multiplicative inverse of an element, you can use the extended euclidean algorithm.


Cryptopals challenge - not understanding the padding details I am working on some tasks in Crypto, specifically on this small task: https://cryptopals.com/sets/2/challenges/9, which I aim to implement in Python.

The point is to add padding for a certain number of bytes, and the value of each byte is the number of bytes added. The example given is "YELLOW SUBMARINE\x04\x04\x04\x04".

I have solved this task I think, but the output is non-displayable. Here is one clean solution I found online

def pad_pkcs7(buffer, block_size):
    if len(buffer) % block_size:
        padding = (len(buffer) / block_size + 1) * block_size - len(buffer)
    else:
        padding = 0
    # Padding size must be less than a byte
    assert 0 <= padding <= 255
    new_buffer = bytearray()
    new_buffer[:] = buffer
    new_buffer += bytearray([chr(padding)] * padding)
    return new_buffer

buffer = bytearray("YELLOW SUBMARINEX")
print str(pad_pkcs7(buffer, 20))

When I run this I get the same result as with my own solution:
YELLOW SUBMARINE[?][?][?][?] (the []s are actually boxes with question marks in them)

My questions:

Why is the padding hex encoded in the first place? Why not YELLOW
SUBMARINE4444? Odd that it is part ASCII and part hex
Did this solution actually solve the problem? Should not the hex-encoded
version of 4 be quite possible to display as 4, 04, \x04?

This is expected behavior when you try to display the byte 0x04, which is not a printable ASCII character.

Padding schemes like pkcs7 operate on byte sequences, not ASCII strings. In general, ciphers and padding routines only care about byte sequences; whether a specific byte corresponds to a printable ASCII character is not important.

The routine uses the byte 0x04 as opposed to the ASCII character 4 (0x34) because it doesn't know or care about ASCII. Also, using decimal digits 0-9 would mean padding can be at most 10 bytes long.

When viewing byte strings in python, you should avoid casting to a string, just keep it as a byte array instead. For debugging, you can do something like

 print pad_pkcs7(buffer, 20).__repr__()


EC: How to prevent discovery of base point after commutative operation If I have a scalar $x$ and point $B$, then I can compute $X = f(x,B)$

If the function $f$ is point multiplication, i.e. $f(x,B) = x \cdot B$, then $B$ can be determined if $X$ and $x$ are known.

Under the circumstances where $x$ and $X$ will be known, is it possible to modify the function $f$ such that $B$ cannot be determined?

It is necessary that:

the function $f$ is commutative, i.e. $f(x, f(y, B)) = f(y, f(x, B))$
$X$ cannot be determined from $x$.
If many pairs of ($x$, $X$) are given out, it cannot be inferred that any two of the pairs were created using the same base point $B$, even if $B$ is not itself determinable.

Edit: It would be fine to limit our choice of $x$ if that would prevent $B$ from being determined.

Edit: The curve used is ed25519

If you're not tied to EC, here's one easy method: let $N$ be a composite number of unknown (secret) factorization; then:

$$f(x, B) = B^x \bmod N$$

is both uninverible, and commutative.  If $f$ needs to be a permutation (that wasn't specified), then we can select the factors $p, q$ of $N$ s.t. $p-1, q-1$ have no small odd factors (and restrict the allowable values of $x$ to small odd values $>1$).

If you absolutely have to do EC, well, the obvious approach would be to actually use a pseudocurve (that is, do the EC operations in the standard way, but work on a ring rather than a field), with the ring being (yes, you guessed it) the integers modulo $N$ (where the factorization of $N$ is secret).  Yes, an operation may fail, but if the factors of $N$ are large enough, this will practically speaking never happen.  $N$ needs to be large enough so that directly factoring $N$ is infeasible (which means it's much larger than moduli we normally do EC in), however it would appear to meet your requirements.  Note that point counting on a pseudocurve doesn't work (or so we hope; if it did, then we could factor), and hence the standard way of inverting point multiplication (which involves finding the multiplicative inverse modulo the order of the curve) is unusable.


Is creating a own protocol safe or should TLS always be used? The more I start to learn about cryptography the more I hear it is unsafe to 'create' your own cryptographic protocol. With this I mean combining cryptographic primitives like HMAC, AES and RSA

However the only protocol, which is also suited for small embedded devices, I know of is TLS. are there any other protocols similar to TLS which can provide: privacy, authentication and verification (identification and trust are not hard requirements). I use these terms as they are described in this explanation of cryptography (i found this to be the best explanation if I want people to know what I'm talking about)

currently I'm just thinking about combining primitives like mentioned above (AES, HMAC, etc) to create a secured communication for my embedded devices but can this be done or should one really try to avoid this? If this should be avoided are there other protocols like TLS which could do what I want?

EXTRA information:
The embedded devices are (often) placed in secure environments, the communication however, is not going through a secure environment.
specs are: 100mhz mcu and about 20 kb ROM/RAM

Designing your own crypto protocol (using existing primitives) is dangerous if you're not sufficiently familiar with cryptographic protocol design and the ways such protocols might be attacked.

If you wish to gain such familiarity, I'd recommend taking a few introductory crypto courses that focus on protocol design and analysis.*  This won't turn you overnight into an experienced protocol designer, but it should at least give you some idea of how much you actually (don't) know about the subject.

Also, regardless of you own skill level, a critical part of designing a secure communications protocol is to get other experienced cryptographers to review it and look for ways to attack it.  Even the most skilled cryptographers can make mistakes and overlook potential attacks, so it's essential to have as many eyeballs on the system as possible.
To paraphrase Bruce Schneier, anyone can design a cryptosystem which they cannot break — what's hard is designing something that others cannot break, either.

This is also one of the main reasons to go for existing standard solutions whenever possible: they've already been subject to more scrutiny by skilled cryptographers than your home-brewed protocol is likely to receive in any reasonable time.  Thus, by leveraging existing standard protocols and implementations, you get to enjoy the benefits of this pre-existing third-party scrutiny.

(Of course, there are standards and then there are standards.  Something published in an IETF RFC or an NIST SP is probably fairly safe (except when it isn't), whereas something found in a random article in The International Journal of Computer Engineering and Agricultural Machinery may actually be complete bollocks.  When in doubt, look for credible reviews by well known competent cryptographers.)

As for TLS specifically, I'd say that it's a good choice in general, but hardly perfect; its major weakness is its complexity, which makes it hard to analyze thoroughly, and easy to make mistakes in implementing it.  Using an existing, thoroughly reviewed implementation helps, but even widely used TLS implementations have been known to carry unfixed bugs for a long time.  Especially on constrained platforms, where the complexity and overhead of TLS may be problematic in themselves, a well written and reviewed custom protocol may sometimes be a better choice than TLS — but it all depends on how carefully the protocol has been designed and implemented.

*) I'm probably not the best person to recommend any specific courses, but in general terms, I've heard good things about Dan Boneh's Crypto I and II on Coursera, for example.  There are also several decent books on the subject, but again, I hesitate to give any specific recommendations for lack of personal familiarity.


Are passwords generated from sine vulnerable to certain attacks? A friend mentioned that he used the sine of a number, i.e. sind(54), to generate long passwords. This way he only has to remember sine 54 and have a calculator to get his password back. I am wondering if this is secure. It can easily generate a long password, but because the numbers are not random would it be vulnerable to some type of attack if they new the numbers were generated using sine?

If someone knows your password creation method, the only hope you have of foiling an attack is if the method has a lot of entropy - roughly, if there are a lot of different passwords you could have with that method (it's not quite the same if some passwords are more likely than others, but it's a good heuristic). If the method is "sine of an integral number of degrees to some precision," this is a fairly weak method. Assuming it's in a base between 2 and 36 (i.e. 0-9 and a-z), and that you only use an integer number of degrees (which means an attacker need only consider integers between -90 and 90), and that the number of digits is between 1 and 15, and that it starts on a digit between 1 and 5, the number of passwords is just $180\cdot 15\cdot 5\cdot 35=472,500$. With a bit of thought, we can guess he's most likely to use base 10 or base 16, and so you just have $180\cdot 15\cdot 5\cdot 2=27,000$ passwords. More thought will reduce the number of likely passwords even further (e.g. if he's doing this for laziness, which is likely, he'll have between 8 and 15 digits starting at the first digit, for 2,880 possibilities).

If the attacker can only try passwords via a web login page, you might not need too many passwords possible to be secure; a login page can lock out the account after 10 tries or similar things that slow down a brute-force. But if an attacker can do an offline attack, it's fairly easy.

Length of a password doesn't determine the security of the password against a smart attacker; entropy does. If I have two possible passwords ("the blue moon rises over the sunny beach" and "colorless green ideas sleep furiously") which I randomly pick between, then an attacker who doesn't know my scheme might have trouble cracking them. But it's better to assume the attacker can figure out your scheme, and only consider how much randomness you inject into each individual password, and in that case my scheme only injects 1 bit despite having long passwords.


DSA with composite p One of the basic requirements of DSA is to choose some prime $p$ of certain bit length. The security then lies in the intractability of solving $y = g^x \pmod{p}$ for $x$.

Is there any “easy” way to solve the discrete log problem when $p$ is composite? I thought about the Chinese Remainder Theorem but can't seem to figure out how it would work. If there is no obvious way to solve for $p$ composite then what is the need for $p$ to be prime?

Is there any “easy” way to solve the discrete log problem when $p$ is composite?

If you know the factorization of $p = rs$, then it can be reduced to solving the problem $y = g^x \pmod r$ and $y = g^x \pmod s$, and then combining the two solutions; hence you're reduced the hardness of the problem to the harder of the $r, s$ subproblems.

If you don't know the factorization of $p$, then it is at least as difficult as factoring $p$ (if you can solve arbitrary discrete logs modulo $p$, then you can factor $p$).

That would imply that the person who generated $p$ might be able to give himself a backdoor (as he'd have an easier time solving discrete logs than anyone else).

On the other hand, that's not the complete story.

You specified DSA; DSA places more requirements on the group it runs in.  For one, it actually operates in a prime-sized subgroup that is both considerably smaller than the modulus size, and which must be listed in the global parameters (as the verifier needs it).  And, in case you're wondering, the fact that the subgroup is prime is important, if it were composite, you could factor it, and attack each of the factors independently.

So, suppose we had $p = rs$ (where the factorization is secret), and we have a generator $g$ with $g^q = 1 \pmod p$ (for some moderate sized prime $q$).

That immediately implies that we have $g^q = 1 \pmod r$ and $g^q = 1 \pmod s$; however, if we have $g = 1 \pmod r$, then a simple computation of $\operatorname{gcd}(g-1, p)$ would reveal the factorization, and hence to be secure, we must have $g \ne 1 \pmod r$ and $g \ne 1 \pmod s$.

This implies that $r - 1 = 0 \pmod q$ and $s - 1 = 0\pmod q$, or in other words, we have:

$$p = (aq +1)(bq+1)$$

where $q$ is public, and $a, b$ are some unknown integers.

If we go through the size of $q$ (perhaps 256 bits), and the sizes of $r = aq+1$, $s = bq+1$ (perhaps 1024 bits each, hence $a, b$ may be 768 bits each), it's not immediately clear whether current lattice based factorization methods would work, but it's closer than anyone would trust.


Secure Secret Sharing to a Distributed Key Setup
There are two groups, $A$ and $B$. Each group is in a Shamir's secret sharing scheme ($t_A$ of $N_A$ and $t_B$ of $N_B$). Each group has a public key that is associated with the identity of the group. The corresponding private keys are distributed among the members and are never reconstructed on any device. Each group has additional secrets as well. Every member has its own public/private key.
Problem
$A$ wants to share a secret to $B$, without reconstructing it and (assuming a threshold number of members in $B$ aren't compromised) without $B$ being able to reconstruct it.
If $A$ knows the scheme and the members of $B$, this is straightforward. $A$ performs a redistribution (like the one described in Verifiable Secret Redistribution for Archive Systems by Wong, Wang, and Wing), encrypting shares for each member in $B$. However, this is annoying because everytime the members or scheme of $B$ changes, $A$ needs to be informed of it.
Instead, $A$ can encrypt shares with $B$'s public key. In this case, how do the members of $B$ know that no member of $B$ can gain access to secret?$^1$
More concretely, there needs to be a group decryption operation for each share, with each decrypted share being available to a different member, such that no other member can see it.$^2$ The issue is assigning shares to different members in a way that replay attacks won't work, i.e., the entire protocol starting over with the same or a different set of $t_B$ members.
Replay Attack 1
Imagine a simple situation where $B$ is in a 2-of-3 scheme. Call the members $b_1$, $b_2$, and $b_3$. $A$ provides two shares in a 2-of-2 scheme, both encrypted with $B$'s public key. $b_1$ initiates the protocol with $b_1$ and $b_2$, gaining access to share 1. $b_1$ then initiates the scheme with $b_1$ and $b_3$, gaining access to share 2. So now $b_1$ knows the full secret without either $b_2$ or $b_3$ having approved of it.
Replay Attack 2
Now imagine a situation where $B$ is in a 2-of-2 scheme. $b_1$ initiates the protocol with $b_2$, getting access to share 1. $b_1$ initiates the protocol again, but this time gets access to share 2. In this application, the member initiating the protocol is the one who has access to the encrypted shares. The initiator provides the data to the other members, who do not have an independent way to get that data from $A$.

$^1$ More precisely, the honest members of $B$ don't want any group with fewer than $t_B$ members to be able to collude together to get the secret.
$^2$ This is a simplification. Since $A$ doesn't know $t_B$, members may end up with multiple shares. This is fine. I'm also assuming there's a max value $t_B$ can take that $A$ can share to, so that at the end of all the decryptions, there's no group of fewer than $t_B$ members that can reconstruct the secret.

From what I understand, you want to share a secret to B in such a way that every single member of B is required to reconstruct the secret. In that case just use a threshold secret sharing scheme where the threshold is the number of players in B. This ensures that no subset of players in B can reconstruct the secret.
I’m not convinced you need encryption here (as secret sharing is already information-theoretically secure. But if you do, then encrypting under public key and sharing to B such that the threshold is equal to the number of shares should suffice.


Deterministic Key using a seed for ECNamedCurve I am trying to generate deterministic keys using EC curve secp521r1 in java. I went through KDF but, couldn't find any references to use it with EC curves. I would appreciate if someone could point me to KDF or something similar to it for deterministic EC keys. All I need is to generate EC key pair using a passpharse.
Sample code that I am using to generate EC keys in Java:
 ECParameterSpec ecSpec = ECNamedCurveTable.getParameterSpec("secp521r1");
        KeyPairGenerator g = KeyPairGenerator.getInstance("ECDSA", "BC");

        g.initialize(ecSpec, new SecureRandom());
        KeyPair pair = g.generateKeyPair();

        KeyFactory fact = KeyFactory.getInstance("ECDSA", "BC");
        PublicKey pub = fact.generatePublic(new X509EncodedKeySpec(pair.getPublic().getEncoded()));
        PrivateKey priv = fact.generatePrivate(new PKCS8EncodedKeySpec(pair.getPrivate().getEncoded()));

The problem is that this requires relatively low level access to the cryptographic algorithms.
In general the private key can simply be set to a set of bits, although it should actually fit in the field. Setting the highest bit to zero is a dirty trick if the runtime(s) do not accept as many random bits as the key size. This will however let you use any kind of KDF to derive the bits.
The public key is nothing more than the private key S multiplied with the generator point. This is where you may get in trouble, as this operation is a low level function that may not be exposed.
In principle you could use ECDH for this using the generator as public point of the "other party", but the Java API is high enough that it won't directly return the resulting point, making this a useless exercise (other API's may differ though, so I thought I should mention this).
So in general you'll need a low level API to perform functions like that.

In your case the best way forward is to use the Bouncy Castle libraries, where such low level functionality is supplied by the lightweight cryptography API. Bouncy Castle also has a nice set of KDF's that you can use. I know 'cause I did the initial implementation.


BB84 Why does Bob generate a random key? I am quite new to this stuff so this question might be trivial. I was reading about bb84 and, as I understood it, after Alice sends $\psi$ Bob chooses a random sequence $b'$ and makes a measurement in either $X$ or $Z$ according to $b'$. After Bob does this he announces that he has received $\psi$ and both him and Alice compare the sequences $b$ and $b'$ discarding the terms for which $b \neq b'$.

What I don't understand: what would be the problem if, after Bob receives $\psi$, he simply announces this fact without choosing $b'$ and making measurements. In this case Alice communicates $b$ to Bob over a public channel and there are no bits to discard.

It seems that Alice has to communicate $b$ to Bob over a public channel in BB84, so why not do it after Bob claims to have received $\psi$?

What I don't understand: what would be the problem if, after Bob receives $\psi$, he simply announces this fact without choosing $b'$ and making measurements.

At the current state of technology, Bob needs to take a measurement of $\psi$ when he receives it; he can't hold it.  It may be that future technology will be able to hold $\psi$ for a nontrivial period of time in an unmeasured quantum state until Alice announces $b$ (and, at that point, Bob cuold then take the appropriate measurement); however, we don't know how to do that now (and it certainly wasn't possible when BB84 was invented).

And, of course, Bob can't measure $\psi$ in both the $X$ and $Z$ basis; that's forbidden by QM (and the security of BB84 relies on that).


Can you help me understand Format Preserving Encryption? I came across the definition of format-preserving encryption (FPE) as first defined in a seminal paper by Black and Rogaway. Based on their paper, FPE (or prefix cipher) is defined as follows (quoted from Wikipedia):

  One simple way to create an FPE algorithm on ${0,...,N-1}$ is to assign a pseudorandom weight to each integer, then sort by weight. The weights are defined by applying an existing block cipher to each integer.

Can you help me understand the difference between this and monoalphabetic substitution, and what security is offered by FPE?

I cannot understand what is the difference with monoalphabetic substitution and what is the security offered.

A monoalphabetic cipher applies to individual symbols of the plaintext.  But an FPE scheme works on the whole message as a unit.  In the set {0,...,N-1} that you mention, N is the size of the message space—the number of distinct messages, not the number of distinct symbols; each number represents a distinct message, not a symbol of a message.  So for example:

For US Social Security numbers, which are 9 digits, N is one billion, and each number in the set {0,...,N-1} stands for a distinct SSN.
Credit card numbers have 16 digits, but generally the first 6 and last 4 digits must be left in the clear, so the middle 6 are encrypted and N = one million.

But the 10 digits left in the clear are used as a "tweak" to the encryption, so that 123456 in the middle six encrypts to different values for different credit card numbers.

The way FPE works is (ignoring the "tweak" concept that I mentioned above):

You define a bijective function between your message space and the set {0,...,N-1}.  For SSNs, N = 1,000,000,000, and the bijective function just treats the 9-digit sequence as a decimal numeral with its most significant digits padded with zeroes.
The FPE scheme gives you a bijective encryption function that takes a secret key and a number between {0,...,N-1} and outputs another number between {0,...,N-1}.  (It also takes a tweak, but I'm ignoring that for simplicity.)

So to encrypt an SSN you convert the SSN into a number using the function from (1), encrypt that number using the FPE scheme, and convert the encrypted number to an encrypted SSN using the inverse of the function in (1).  To decrypt you use the inverses of the functions.

One of the reasons why FPE scheme is defined in terms of sets {0,...,N-1} for user-chosen values of N is for flexibility; as long as you can define a bijection between your message space and such a set, you can use FPE to encrypt those values.  For example, if you want to apply FPE to a database date field, you can't just read the date's sequence of digits as a number, because some such sequences of digits aren't valid dates (e.g., 2014-54-35), but the encryption could well output the number 20,145,435.  But you can use date arithmetic to represent a date as a count of days since a reference "beginning of time," and then apply FPE using this bijection.

The security offered gets a bit more complex, but at the most basic level it is that the FPE is a pseudorandom permutation on the set {0,...,N-1}.  Imagine a solution where instead of using a cipher, you had a big database where, for each plaintext Social Security number, you stored a unique, randomly chosen sequence of nine digits.  The encryption operation would go somewhat like this.  Given a plaintext P:

Search the database for an entry that has P as its plaintext.
If P is already associated with a ciphertext C, then return C;
Otherwise, set C to some message chosen at random (using a true random number generator).
Search the database for an entry that has C as its ciphertext.
If C is already in the database, go to 3.
Otherwise, store the entry (P, C) in the database, and return C.

FPE's basic security goal, put in simplified terms, is to be no worse than that in practice, from the point of view of an attacker who has doesn't have the encryption key but might have seen a subset of the plaintext/ciphertext pairs.

Note as well that there exist token vault solutions that work like the six-step sketch that I described—a database that associates plaintext with unique random values.  So in another sense, the security goal of FPE is offer comparable practical security but at lower cost and better reliability and performance.


How to perform Shamir Secret Sharing with a Tabula Recta? In this post, a couple comments suggested that a tabula recta could be used to perform Shamir Secret Sharing.  I'm specifically interested in this statement:

  you could just have a table of all 100 inverses mod 101

If this simply means a 10x10 table, that's no problem.  That's smaller than a regular tabula recta.  But even if it's 100x100, I am still interested in how this would work.

Taking the question as literally as possible, I have provided my pencil and paper tables for a scheme among three parties with a polynomial of degree 2 and a field of $\mathbb{Z}_5$ to keep things feasible for a pencil and paper example. Given the tables, in order to reconstruct any secret look up the table to be used by the share from party 1 (table numbers are denoted in a box to the upper left of each table), the row to be used by the share from party 2 and the column to be used by the share for party 3.

I've provided an example polynomial $4x^2+3x+1$ which evaluates correctly to 1, the secret, at $x=0$, 3 when $x=1$, 3 when $x=2$, and finally 1 when $x=3$. Then, to reveal the secret, take these shares and look them up as described. I've boxed in red the correct value from following the described procedure. This set of tables should work for any polynomial valid in the field described and for shares based on players associated with the same values for $x$.
$\mathbb{Z}_5$">


How to compare the efficiency of public key cryptosystems, i.e., RSA vs El Gamal? As part of my Mathematics degree I'm taking a Discrete Mathematics module which partially covers Public Key Cryptography but does not at all enter it in depth.

I'm currently working on a project that involves writing about the process, security and efficiency (in terms of calculation/processing speed) of a few PKC systems.

I understand the processes and how to discuss the security of these systems, but I'm struggling with what makes a PKC system "good" in terms of efficiency, at least comparatively. I'm only considering the following 3 systems:

RSA,
El Gamal, &
Knapsack.

On a basic level I can compare key sizes and ciphertext expansion, but further than that I'm a bit lost; especially in terms of terminology when attempting further reading. Any direction or advice would be greatly appreciated.

Since you are approaching this from the point of view of mathematics, I think the most fruitful avenue would be to look at asymptotic performance and security of the problems that the cryptosystems are based on.

For example, with RSA you need a modular exponentiation for every message you encrypt or sign. The time that takes depends on the length of the modulus as well as the exponent. The most efficient general purpose algorithm for breaking RSA is GNFS which also takes time dependent on the size of the modulus.

Find out the same for the other algorithms you are interested in and you can compare them and see e.g. whether one will asymptotically become more efficient at equal security.

This will allow you to steer clear of the various practical issues of how the different constants compare and what platform some performance measures might be relevant for.


RSA key requirements so that it can decrypt a DES key I came upon a solved exercise that uses a client's RSA key to encrypt a DES key. It has the following phrase:

value of n for RSA key generation has been chosen accordingly so that the DES key can be encrypted.

However it does not go on to explain what the requirements are and why. Could someone point this out to me? Many thanks.

A DES key is 56 bits long or 8 ASCII(7 bit) characters.
The rsa public key n must be larger than that.
However RSA key only barely big enough to hold a DES key would give almost no security at all.
Common RSA key lengths today are 2048 or even 4096 bits long.
512bit RSA keys which used to be reasonably common can now be broken in minutes with commercially available cloud services. So big enough to be even remotely secure will be much bigger than the minimal size to encrypt a DES key.
P.s
If you want to use OAEP (and you do) you need some extra wiggle room beyond the raw message size but still don't go anywhere near secure key length.


In a group, is it hard to calculate the base $g$ given $g^a$ and $a$? Discrete logarithm, that is: calculate $a$ given $g$ and $g^a$, is assumed to be a hard problem in some groups.

Is it also hard to calculate $g$ given $g^a$ and $a$?

It depends. If the order $m$ of $g$'s group is known and $a$ has an inverse modulo $m$ (which is the case if and only if $a$ is coprime to $m$), then it is easy: Calculate the inverse $b:=a^{-1}\bmod m$ (for instance, using the Euclidean algorithm), and compute the power $(g^a)^b$. By Lagrange's theorem, this equals $g$.

However, there are cases for which it's hard: for example, when $n=pq$ is the product of two unknown primes $p,q$ and $g\in\mathbb Z/n\mathbb Z$, then the task is equivalent to decrypting the RSA ciphertext $g^a$ with respect to the public key $(n,a)$, which is generally assumed to be hard.


How is XOR used for encryption? I am a programmer, so when I hear XOR, I think about the bitwise operator (e.g. 0110 ^ 1110 = 1000).

The mention of "XOR" comes up quite a bit in cryptography. Is this the same XOR as the bitwise operator? If so, how is it used to encrypt a large amount of data rather than just an integer? Wouldn't you need the "password" to be the same length as the data you are encrypting?

Yes, it's the same XOR. It gets used inside most of the algorithms, or just to merge a stream cipher and the plaintext.

Everything is just bits, even text. The word "hello" is in ASCII 01101000 01100101 01101100 01101100 01101111. Just normal bits, grouped in 5 bytes. Now you can encrypt this string with a random string of 5 bytes, like an One-time pad. Let's say we got the randomly generated string 10001001 10000010 00001011 01001101 11101101 (generated with www.random.org). Now we XOR both strings, getting 11100001 11100111 01100111 00100001 10000010. If you never reuse or reveal the key, nobody can crack this cipher. (Well, I did reveal the key, so it's not secure anymore.)

Many block ciphers use XOR. Let's take AES: The Advanced Encryption Standard uses xor on single bytes (some other algorithms use blocks of 16 or 32 bits; there's no problem with sizes other than 8 bits). The round key will be XORed with the intermediate result and after that permuted and substituted. XOR also gets used in the key shedule.

IDEA also uses XOR as one of its three main functions: XOR, addition and multiplication.

XOR has (inter alia) these advantages when used for cryptography:

Very fast computable, especially in hardware.
Not making a difference between the right and left site. (Being commutative.)
It doesn't matter how many and in which order you XOR values. (Being associative.)
Easy to understand and analyse.

Of course, some of this "advantages" can be disadvantages, depending on the context. The fast speed makes it possible to use XOR often without huge performance drops. The security of Threefish, another block cipher, relies on the non-linearity of alternately using modulo addition and XOR. Despite of the use of 72 rounds (as the base of the hash function Skein) it's still quite fast.

XOR alone is not enough to create a secure block or stream cipher. You need other elements like additions, S-boxes or a random, equally long bit stream. This is because of the linearity of the XOR operation itself. Without non-linear elements, a cipher can easily be broken. See Why do block ciphers need a non-linear component (like an S-box)? for more details on why non-linearity is important.


what is an injective trapdoor function? The answer to this question at Crypto.SE is clear about what a trapdoor function is, but what makes a trapdoor function "injective"?

A trapdoor one-way injection is a trapdoor one-way function such that two different elements

of a single domain are never mapped to the same element of the corresponding codomain.

By Goldreich-Levin, if there exists an trapdoor one-way injection

then semantically secure public key encryption exists.


Is Paillier secure from known plaintext attack for single character message? Assuming I have three messages m1,m2,m3 where m1=m2=m3=1 and I compute c1,c2 and c3.

Does that mean that c1=c2=c3 in cipher-text from ?
If not, how many times can I encrypt a message m=1 and still produce a unique cipher-text ?

if not possible, can I solve the problem by putting Zeros as padding and still use the additive property ? (e.g. m1=01...m2=001 and m3=0001 and when I calculate x=c1+c2+c3 the decrypted result D{x}=3)

I just started working with cryptography, so please be understanding. :-)

Yes, Paillier encryption is secure from known plaintext attack (for single-character message, and any other supported message size). With high likelihood, three ciphertexts $c_1$, $c_2$ and $c_3$ for the same plaintext will be different.

When using public modulus $n$, each Paillier encryption draws a uniformly random number $r$ in range $[0,n^2)$ (in some descriptions: coprime with $n$, but that's overwhelmingly likely for secure choice of $n$, thus can be omitted). Different $r$ will lead to different cryptograms $c=g^m\cdot r^n\bmod n^2$.

For proper implementation, by the birthday problem 101, the probability is about $k^2/2n^2$ that among $k$ ciphertexts for the same plaintext, any two are equal. For security against factoring, $n$ must have some thousand bits, thus said probability is entirely negligible for any feasible $k$ and secure choice of $n$. It is much more likely that whatever generates $r$ gets defective, and hickups, leading to identical ciphertexts.

Note: Pailler encryption is homomorphic only for messages that are straight integers $m$. Padding with zeroes on the left can't change $m$ if the homomorphic property must remain.


How to choose an algorithm I have some understanding of Cryptography and I would like to know if there is a tool or website to help me choose an algorithm based on my own needs (I'm being vague in purpose).

I'm looking for a website or tool that shows properties of algorithms like:

What is it best for
What is it not very good for
How can it be used poorly
What kind of algorithm is it? (hash, encryption, etc)
Is it reversible?
Is it symmetric or asymmetric?
Does it have known vulnerabilities?
How strong is it against brute force?
How proven is it in the industry?
When was it invented?
Is it fast to run? To decrypt (as appropriate)?
How common are implementations of it in various languages?
What programming languages have implementations currently?

I specifically want information to help me choose the appropriate algorithm based on my needs, not just encyclopedic information about algorithms. And for vulnerabilities, a resource that is maintained and updated would also be invaluable.

Perhaps all this information does not reside in one place, but I'm not really sure where to even start (other than just googling 'how to choose an encryption algorithm' and etc) to research this information.

Edit: Adding some links to articles

Wikipedia category: Cryptographic algorithms
Wikipeida: List of algorithms, Cryptography

There is no out of the box tester which can tell you what you need, you need to do research. I'm having the same 'problem'. I'm doing an internship for a company which wants to protect their self-created protocol which works on top of TCP.

So to tackle this I've create a plan of approach and defined my research parameters (quite broadly). Now i'm looking into the history of several algorithms (RC6, AES, Twofish) and looking which is best applicable to my situation.

Since i have hardware restrictions (it's for embedded use and some embedded divces they use are OLD) so I'm currently looking into libraries such as PolarSSL to find C implementations of cryptographic algorithms to test on the embedded devices i have.

When i test them i'll test for speed, code space and other things.

So in short, what you need all depends on what you need, maybe TDES even though it's old and almost insecure is what you need. but you need to do your own research.

As far as good implementations are concerned, open source libraries is the way to go. They are used world wide and it is safe to say well known open source libraries have been tested to an extend no stack overflow solution has (given the solution isn't a direct copy of an open source library :P )

But for all your questions these websites are for your best research:

NIST publications,  proven secure algorithms (no implementations
but lots of background)
Wikipedia, General background and    specifications
PolarSSL Source code in C
For implementations in for example c# the .net library has everything you could possible need.

So final note do not create your own implementation! use the libraries but that's a disclaimer everyone should know by now :P


Is the Caesar cipher really a cipher? In this lecture by Dan Boneh on Coursera it was stated at minute 03:37 that

  The Caesar cipher, actually, is not a cipher at all. And the reason is that it doesn't have a key. What a Caesar cipher is, is basically a substitution cipher where the substitution is fixed.

Can someone elaborate what he said? I don't get the part that he says that it doesn't have a key.

He is talking about the original version of the Caesar Cipher where the substitution was just a +3:
A -> D
B -> E
C -> F
D -> G
E -> H
F -> I
G -> K
H -> L
...
X -> A
Y -> B
Z -> C

Because the shift is fixed, it does not have a key (but you could say it is a substitution cipher with a key equal to +3).
However it is common usage to call a substitution cipher as a Caesar Cipher because the idea the same but where you change the value of the shift.

The Caesar cipher is named after Julius Caesar, who, according to Suetonius, used it with a shift of three to protect messages of military significance. While Caesar's was the first recorded use of this scheme, other substitution ciphers are known to have been used earlier.
If he had anything confidential to say, he wrote it in cipher, that is, by so changing the order of the letters of the alphabet, that not a word could be made out. If anyone wishes to decipher these, and get at their meaning, he must substitute the fourth letter of the alphabet, namely D, for A, and so with the others.
— Suetonius, Life of Julius Caesar 56 [source]


DSA: If signature is accepted then signature is correct In one my classes, I have the following exercise:

  Prove that, in the DSA signature scheme, if a DSA signature is accepted, it is also correct.

How would I go about proving this? In cryptography, what is one usually referring to when saying a signature is correct? Does it mean that if the verifier accepts the signature, then it was signed with the correct private key?

This isn't completely standard terminology, so you should check the precise definitions in your lecture notes. But I can't think of anything else that the exercise should be.

You have a definition of the DSA signature process: given some parameters $(p,q,g)$, a private key $x$ and a message $m$, generate a nonce $k$ and calculate $(r,s)$ given by a certain formula. You also have a definition of the DSA verification process: given some parameters $(p,q,g)$, a public key $y$, a message $m$ and a candidate signature $(r,s)$, make a certain calculation and output “accepted” or “rejected”. This is a signature scheme if every output of the signature process is accepted by the verification process, that is, if you take the $(r,s)$ given by signing and perform the verification process on it, the output is “accepted”.

This exercise asks you to prove a dual property which is a practical necessity, while not sufficient for security: given parameters $(p,q,g)$, a key pair $(x,y)$ and a message $m$, if the verification process for $y$, $m$ and the signature candidate $(r,s)$ outputs “accepted”, then there exists a nonce $k$ such that the signature process for $x$ and $m$ yields the output $(r,s)$.

   The calculation itself is easy: take $k = s^{-1} (m + x\,r)$, inverting the formula used to compute $s$ from $k$ and $r$ during the signature process. The verification process basically checks that $g^k = r$, so if the signature is accepted, that means that it's the output of the signature process for this $k$.

This property is practically necessary for security because if the adversary can efficiently find $(r,s)$ which is not the output of the signing process, that means that they can craft an invalid signature. I'm not sure if the mere existence of a valid signature that no one can find efficiently would disqualify the signature scheme.


Enhance security by combining bits of 4 different hashes Assuming that performances do not matter, is there any real benefit in terms of security (in general) in combine hashes in this way:

hash functions:

Blake512 (b)
Groestl512 (g)
Kekkack512 (k)
Skein512 (s)

Output:

## imagine the outputs of each function as 512 single bit:
b1b2b3b4......b512
g1g2g3g4......g512
k1k2k3k4......k512
s1s2s3s4......s512

Mix:

## combine the top 128bits of each output into a 512-bit hash
b1g1k1s1 + b2g2k2s2 + ....... + b128g128k128s128

Does this make sense?
If yes, do I loose security (in general) by truncating each hash to 128 bit?

ps. it's not meant to store passwords

The main question about this topic is: Guarding against cryptanalytic breakthroughs: combining multiple hash functions. There you will find some better combiners for multiple hash functions. I would generally recommend against the extra complexity - a single good hash ought to be enough.

Now, regarding your way of combining them:

  Does this make sense? If yes, do I loose security (in general) by truncating each hash to 128 bit?

By truncating a hash to 128 bits you make brute force attacks against the hash easier and may also make other attacks easier. A 128-bit hash alone would not be secure, since a $2^{64}$ collision attack is within plausible estimates of strong attackers' (e.g. national security agencies') capabilities.

Some hash functions, e.g. SHA-2, explicitly state that you can truncate them and assume the lower resistance implied by the shorter output size. Others do not.

By concatenating four 128-bit hashes you are back to "secure against collision attacks" if at least two of them are 64-bit secure. (Preimage attacks are another matter. It depends on which notion of preimage resistance you consider, but if one of the hashes somehow leaked some bits of the input you could lose preimage resistance.)


Reproducing RSA GCD attack (common factor) - real world certificates I'd like to reproduce common factor attack on rsa.
And wondering how to get as many as possible (milions?) real world rsa certificates.
Any ideas?

There are multiple steps you'll need to reproduce the attack done by different teams in 2012:

Firstly, you effectively need to grab the data you'll need consecutively. You might take the X.509 certs proposed by third parties, such as scans.io or the SSL Observatory; or grab it yourself directly as explained by Pedro (although I guess it might be easier to use specialized fingerprinting tools to pull them quickly instead of a script relying on OpenSSL).
Secondly, you need to extract the interesting data out of the certificate, this shouldn't be too hard, just make sure you can link the data back to where it came from. What you need to find is just the modulus used in each certificate and collect those in a big database.
Finally you need to perform batch GCD on the huge list of modulus you've extracted from those certs... That is probably the hardest part, I don't know if there exists distributed algorithms to perform it easily without having tons of RAM under the hand...

Now since you seem especially interested by how you could perform 1., you might also want to pull out all of the SSH keys you can find on the web, since most of them will also be RSA keys, as well as PGP keys (which was also done in one of the papers).
I've also once read a blog about doing this on Github's user SSH keys as well, but this would take months to perform, since Github has strict rules regarding its API and requests' rate.

Finally another team has built a key analyzer using the same methods to test your key against millions of other keys (and allowing them to build a bigger database at the same time, obviously): https://keytester.cryptosense.com/


Is there a cryptographic function or system in which it becomes HARDER to break as time passes? Is there a function or system which is time depending in which the effort required to brute force the decryption increases with time? It is easy to break encryption from many years ago because computers are so much faster. Is there a system in which time is a component and as time passes then it gets harder & harder to decrypt? Perhaps there is a physical entropy component which degrades after time? Something akin to disappearing ink, but digital.

Any protocol with long-term security becomes harder to break after the protocol execution has finished.

In the Bounded-Storage Model, protocols become harder of break as [information about the

randomizer that's not stored by the adversary] is lost. $\:$ (This point is similar to minar's observation.)


Possibility of factorisation of rsa modulus due to vulnerability in java implementation code Below is my implementation of the RSA algorithm. Actually I'm choosing the private key (d) instead of public key (e) and computing the public key.It is working fine but

I want to know if this is a safe implementation? and also Is any part in the code could lead to factorization of the modulus (n), thereby breaking the key?

As I did some work on it, I think the way I'm calculating (e and d) that could leads to factorization of the modulus(n) but I'm not sure. I read some research work on vulnerable class of exponents in RSA and from there I got public exponent satisfying an equation:

eX - NY = (ap + bq)Z with q>a>0, b=[ap/q]

Using the continued fraction algorithm and the Elliptic Curve Method of factorization, we can show that such exponents yield the factorization of the RSA modulus.

So question is that IS any part in code could lead to factorization of the modulus(n), thereby breaking the key? If yes then which part?

import java.math.*;
import java.security.*;
import java.util.*;

public class RSAKeyGenerator
{
        public static int KEY_SIZE = 2048;

        public static void main(String [] args)
        {
    try
    {
    //select size of each prime factor whose product will be atleast the given keysize.
    int factor_size = KEY_SIZE/2;
    Random rnd = new SecureRandom();
    BigInteger p = BigInteger.probablePrime(factor_size, rnd);
    BigInteger q = BigInteger.probablePrime(factor_size, rnd);
    //compute N = p * q
    BigInteger N = p.multiply(q);

    //compute euler phi = (p-1) * (q-1)
    BigInteger phi = p.subtract(BigInteger.ONE).multiply(q.subtract(BigInteger.ONE));

    //select d size
    int d_size = KEY_SIZE / 5;

    //compute d
    BigInteger d = BigInteger.probablePrime(d_size, rnd);

    //make sure d is a coprime to euler phi.
    while (phi.gcd(d).compareTo(BigInteger.ONE) > 0)
    {
        //select another d

        d = BigInteger.probablePrime(d_size, rnd);
    }

    // compute e = d^-1 mod phi
    BigInteger e = d.modInverse(phi);
    BigInteger plaintext = BigInteger.probablePrime(d_size, rnd);
    BigInteger ciphertext = plaintext.modPow(e, N);
    BigInteger decryptedvalue = ciphertext.modPow(d, N);
    if(decryptedvalue.compareTo(plaintext) == 0)
    {
        System.out.println("decrypted values matches original plain text. these are proper RSA keys");
    }
    else
    {
        System.out.println("something wrong... decrypted value does not match. try again!");
        return;
    }

catch (Throwable th)
{
}

}

No, this is not a safe implementation; from the modulus and the public exponent, it would be possible to factor the modulus.

The reason is that you pick the private exponent to be small; one-fifth the size as the modulus.  It's known that knowledge of a public exponent corresponding to that is sufficient to factor.

The obvious question is "why are you picking the private exponent?".  Instead, why don't you pick the public exponent (65537 is a popular choice), and derive the private exponent from that.


Manipulate encrypted file: AES / ECB / PKCS5Padding As part of a competition I want to manipulate (or decrypt) a file. I know, that the file contains gzip compressed text and is encrypted with AES / ECB / PKCS5.
I also have the plain text and the cipher text of that file. I don't know the secret key. What would be a strategy to manipulate this file, so that afterwards it could still be decrypted and decompressed with the same secret key and the plain text would be different from the original one. Is that possible at all?

A block cipher is a permutation of all possible plaintext blocks and ciphertext blocks. That is: each plaintext block has a corresponding ciphertext block and vice versa. Which one depends on the key and direction of operation (encryption or decryption).

Now ECB just results in a succession of the plaintext blocks converted to ciphertext blocks. There are two things to notice: if a ciphertext block is changed then decryption of that block will always result in a different plaintext block. However, because you don't know the key you don't know which one. So unless you can choose a ciphertext block for which you know (part of) the plaintext, the result will be indistinguishable from random.

If you do know (part of) the plaintext for a ciphertext block then you can use this knowledge to put this plaintext block anywhere in the ciphertext. So you can reshuffle, delete blocks, duplicate blocks and put in blocks for random plaintext as you wish. However, you should always keep to blocks, not individual bytes.

There is only one rule when doing this: the last block should be left alone otherwise the unpadding is likely to fail. You should only replace it with a ciphertext block with correct padding, if at all (you may have received a previous message encrypted using the same key with a known plaintext/padding block that you can reuse).

Note that you require authenticated encryption or encrypt-then-MAC (with MAC'ed or known IV) to avoid the problem of replacing plaintext. Just using CBC or CTR mode - for instance - doesn't protect the plaintext message in any meaningful way.


Does passphrase length impact read-write speed? I'm using Diskcryptor to encrypt a 2TB external USB HD and the process is taking over 2 days. I chose a 100-character strong encryption key passphrase (because, why not?) and am now wondering if the length of the key passphrase has any impact on how long it takes to encrypt the drive. I'm also wondering if the length of the key passphrase will have an impact on how long it takes to write and read files from the encrypted drive. If I had chosen a 25-character key passphrase would this process be faster? Would reading and writing from the drive be faster?

Update: It has been explained to be below that what I was calling the encryption key is in fact the passphrase.

If I had chosen a 25-character key would this process be faster?

That would depend entirely on how Diskcryptor was designed; but it appears it would not.

According to the Diskcryptor homepage, Diskcryptor selects a random symmetric (AES, Twofish or Serpent) key, and uses that to encrypt the disk; it uses the passphrase (what you call the strong encryption key) to encrypt that random symmetric key and put it in the boot sector.  When it comes time to use the disk, you'd enter your passphrase, which would allow Diskcryptor to decrypt the random symmetric key; that symmetric key is then used to decrypt (and encrypt) everthing else.

Because the vast bulk of the work is done using that random symmetric key (which is the same size independent of the size of the passphrase), the length of the passphrase doesn't matter.

Now, the page does mention that it can use Cascaded ciphers; say, AES + Serpent.  If you have it configured that way, it would be considerably slower than if you were just using AES (which would be easily the fastest because of the AES-NI instructions); that's the only thing I can think of which might be slowing you down.


Is it a bad idea to use PGP encryption for structured/predictable data? I'm working on an app and need to encrypt some structured data. The data will be turned into a string form (JSON) before getting encrypted.

The data format I'm using will always start with a { character and end with a } character. Does this make encryption less secure? Are there any methods for more securely encrypting a JSON string?

There are no known-plain-text-attacks known for the symmetric encryption protocols used by OpenPGP with the OpenPGP CFB mode in use, so you can safely rely on it.

In the end, the very first few bytes of OpenPGP packets are generally rather easily guessable by design, as they usually introduce a compression-packet and literal (data) packet with either very small parameter ranges each -- and this is not considered a problem for OpenPGP but for some very esoteric and hardly usable adaptive cypertext attack relying on a decryption oracle, that is partially exploiting this.


Do the elliptic curves over prime fields must always contain prime number of elements (prime order)? I have gone through one example where i saw a curve defined over some prime number containing non-prime order.

In general, an elliptic curve over $\mathbb{F}_p$ can have a nonprime order.
Much more is known.

As mentioned in Stinson's book Cryptography:Theory and Practice, 2nd Edition, Theorem 6.1, the additive group of an Elliptic curve $E$ over $\mathbb{F}_p$ with $p>3,$ and prime, is isomorphic to $Z_{n_1}\times Z_{n_2}$ with $$n_2|n_1,\quad n_2|(p-1).$$


How to detect if n long messages have encrypted with the same one-time pad? I have a slight idea on what the attack would be. But my question is: how would one detect if n long messages (n>5) have been encrypted with the same one time pad, K?

Specifically, the $K(K-1)/2$ symbolwise difference of the, say $K$, messages should obey the plaintext distribution. If the plaintext is in a natural language, patterns can be detected using various techniques.

If the messages are binary $n=5$ won't be nearly enough. If the messages are in ASCII, $5$ symbols yield 40 bits, so that might be enough, and you'd even rule out key guesses that don't yield printable ASCII characters when XORed with ciphertext.


Multi-secret sharing (Packed secret sharing) - Some questions In the publication - "Communication complexity of secure computation", I have encountered a small problem - on page 5 of the literature under the heading "Theorem 1" they have described a $(c,d; k,n)$ multi-party secret sharing scheme.
Here, $d$ denotes the minimum number of parties that must come together to recover the secret, $k$ denotes the number of secrets, $n$ denotes the number of parties and $c$ denotes the maximum number of parties who together cannot gain any further information about the secret by collaborating.
I quote the text when it describes a $(t - k + 1, t + 1, k , n)$ multi-secret sharing scheme - (note $k \leq t< n$).

Theorem 1: There is a $(t– k+ l,t + 1; k,n)$- multi-secret sharing
scheme to share $k$ elements of a finite field $\mathbb{F}$ among $n$
players, with $k < n,$ where each multi-share is a single element of F.
Proof: Let $S_1, \ldots,S_k$ be the Dealer’s secrets. Assume that
$a_l,....,a_k$ and $e_l,....,e_k$ are pre-selected elements
of $\mathbb{F}$ that are known to the Dealer and all $n$ players.
A generalization of
Shamir’s secret-sharing scheme suffices. In the Distribution Phase,
each player $i$ receives the multi-share $p(a_i),$ where $p(x) \in F[x]$
is an otherwise random degree $t$ polynomial such that
$$p(e_i) = S_i, 1 \leq i \leq k.$$
More specifically, $$p(x) = q(x) \prod_{i = 1}^{k}(x – e_i) + \sum_{i = 1}^{k}S_i L_i(x),$$ where $q(x)$ is
a completely random degree $t – k$ polynomial, and where $L_i(x)$ is the
Lagrange polynomial.

i. I seem to only see the $k$ multi-shares distributed to k out of n parties. Is this understanding of mine incorrect? What is the role of the other $(n-k)$ parties?
ii. Are there any further resources online that I could refer to for such multi-secret sharing schemes? (preferably not academic literature as I'd like to work through some examples.)
Thanks very much in advance.

I believe there is a typo in the paper: instead of $k$ elements $a_1, \dots, a_k$ there should actually be $n$ fixed public elements, i.e. $a_1, \dots, a_n \in \mathbb F$. To secret-share, first determine $p(x)$ based on the dealer's secrets. Then, give $p(a_i)$ to player $i$ for each $1 \leq i \leq n$.


Variation on the ECB Penguin problem So this is an age-old example of why encrypting images with ECB is a terrible idea, since the underlying pattern of the image remains the same. Referenced from: If you encrypt an image (AES), is it still an image and can you view it?

In this question, the answerer shows that is is easy to reconstruct an image (in the ppm format) with:

# First convert the Tux to PPM with Gimp
# Then take the header apart
head -n 4 Tux.ppm > header.txt
tail -n +5 Tux.ppm > body.bin
# Then encrypt with ECB (experiment with some different keys)
openssl enc -aes-128-ecb -nosalt -pass pass:"ANNA" -in body.bin -out body.ecb.bin
# And finally put the result together and convert to some better format with Gimp
cat header.txt body.ecb.bin > Tux.ecb.ppm

The variation in this particular question is that, 1. I do not know what the header is, and 2. The header is not separated from the image.

To elaborate, let's say that I have a file called Tux.ppm which I encrypt as follows:

admin@ubuntu32:~/Documents$ openssl enc -aes-128-ecb -nosalt -in Tux.ppm -out image.bin
enter aes-128-ecb encryption password:
Verifying - enter aes-128-ecb encryption password:

Though it is not relevant to the question, for the sake of completeness, the encryption password used was foo.

Now, if I know what the header initially looked like, reconstructing the image is simple. Say, if I know that the header for Tux.ppm was:

P6
265 314
255

Then, if I simply create a new file, call it header.txt, add the above content to it, and execute:

cat header.txt image.bin > sampleTux.ppm

Then sampleTux.ppm is still entirely recognizable:

Nevertheless, the illustrate a certain point, if I mess the header up just a little bit (e.g. modify the width to 275 and the height to 324), the image screws up beyond recognition.

Say that I've now been given a file called image2.bin. I know that this image was initially a PPM image which was encrypted like above (i.e. it was encrypted with its header). I know that it is a P6 type image which uses the 255 color-encoding format. What I don't know is the width and the height of the initial image, so I cannot construct a new header for it.

How can I create such an "ECB Pengiun" for image2.bin? How can I get information about its initial width and height without guessing it (if that is at all possible)? As illustrated above, that width and height has to be quite exact, otherwise the image completely distorted.

EDIT: In the interest of making better guesses. Assuming that the image not compressed and was created from a standard A-series (A4, A5, etc.) paper, I know that is has a ratio of length-in-millimeters = sqrt(2) * height-in-millimeters. Furthermore, it has a possible DPI of 72, 150, 300 or 600... which still leaves a lot of possibilities.

Maybe I could narrow down the possibilities further if I knew the amount of pixels in the initial file? Could I just get this information from the size of image2.bin or would I have to do something infeasible such as reverse-engineer the process which AES encrypted the file in the first place?

You cannot, at least not if that's the only encrypted image. ECB leaks information because repeated plaintext blocks lead to repeated ciphertext blocks. But it doesn't leak the information within those blocks directly.

So you could find the original size by finding another encrypted picture with the same header of which you already know the size. In that case the encrypted header should be identical.

Otherwise, smart guessing might be the best way forward. If you look at the vertical lines then there should be a high amount of repetition between one horizontal line and the next. Just shifting the image and selecting the one with the most vertical repetition should do the trick.


Mathematics behind the paper "how to leak a secret" for ring signature I'm reading the paper "How to Leak a Secret" (Rivest, Shamir, Tauman; 2001).

On page 8/14, in chapter 3.4, the authors present the following "combining function":

$$C_{k,v}(y_1, y_2,\ldots,y_r) = E_k(y_r \oplus E_k(y_{r−1} \oplus E_k(y_{r−2} \oplus E_k(\ldots \oplus E_k(y_1 \oplus v)\ldots)))) .$$

Is there any explanation for why this function satisfies the second one of the three properties listed on the previous page:

  Efficiently solvable for any single input: For each $s, 1 \leq s \leq r$, given a $b$-bit value $z$ and values for all inputs $y_i$ except $y_s$, it is possible to efficiently find a $b$-bit value for $y_s$ such that $C_{k,v}(y_1, y_2,\ldots,y_r) = z$.

A concrete example of how to solve it would be ideal.

From the paper, $E$ is a cipher, i.e., $E_k$ is a permutation. That is, given a secret key $k$, one can compute both the encryption $y=E_k(x)$ (for any $x$) and the decryption $x=E^{-1}_k(y)$ (for any $y$). Therefore, if you know $z$ and all but one $y_i$, you can pick a $v$ (which equals $z$ in the context of ring signature) and get the missing $y_s$ by computing the XOR of $s-1$ $E_k$ encryptions starting from "inside" of the $E(E(...))$ expression and $r-s$ $E_k^{-1}$ decryptions starting from "outside". For instance, if $r=3$ and $s=2$, then $y_2=E_k(y_1\oplus v)\oplus E^{-1}_k(E^{-1}_k(z)\oplus y_3)$.


Hash collision resistance requirements for Lamport signatures According to the original paper, Lamport one-time signature scheme uses two one-way functions: $F$ and $G$. The former one, $F$, is used to create a public key by hashing elements of the private key (and also for hashing signature elements when verifying it); the latter, $G$, is used to hash a message when signing and verifying to get the number of bits corresponding to the number of pairs in keys.

As far as I understand, the requirement for $F$ is that it must be resistant to preimage attacks, and $G$, in addition to this, must also have collision resistance.

Given the standard hash function that satisfies all these requirements, I assume that $F$ and $G$ can be the same, e.g. SHA-256, which provides 256 bit security against preimage attacks and 128 bits security against collision attacks. Using it, we have the following key and signature sizes (described as dimensional arrays):

 Private key: [256][2][32]byte   (16 KiB)
 Public key:  [256][2][32]byte   (16 KiB)
 Signature:   [256][32]byte      (8 KiB)

My question is: if we're aiming for overall 128 bit security, can we reduce the output of $F$ to 128 bits instead of 256 bits, leaving $G$ as is. Does $F$ require collision resistance?

For example, if we use SHA-256/128 for $F$ and SHA-256 for $G$, this will give us the following sizes:

 Private key: [256][2][16]byte   (8 KiB)
 Public key:  [256][2][16]byte   (8 KiB)
 Signature:   [256][16]byte      (4 KiB)

Will this give us 128-bit security?

On the Wikipedia page describing Lamport signatures, there's this paragraph:

  For each private key $y_{i,j}$ and its corresponding $z_{i,j}$ public key pair, the private key length must be selected so performing a preimage attack on the length of the input is not faster than performing a preimage attack on the length of the output. For example, in a degenerate case, if each private key $y_{i,j}$ element was only 16 bits in length, it is trivial to exhaustively search all $2^{16}$ possible private key combinations in $2^{15}$ operations to find a match with the output, irrespective of the message digest length. Therefore a balanced system design ensures both lengths are approximately equal.

However I fail to understand it: what are input and output and what message digest length (is it the length of output of $G$, $F$, or both), which part refers to the number of elements in keys and which part refers to the length of a single element? I'd appreciate a better explanation. Thanks!

Yes, it makes sense to truncate the hash to 128 bits. The security proof actually says that if finding a preimage for F requires effort $2^{n}$, then breaking the Lamport signature scheme with $G$ having k-bit digests requires effort $2^{n}/2k$. So strictly speaking, with $F$ truncated to 128 bits and $G$ having 256 bits $(2k=512=2^{9})$, you will have $128-9=119$ bits of security.

This is not an artifact of the security proof: since there are $256*2=512$ public keys, an attacker has 512x more chances to find a preimage compared to a normal, single preimage attack.

In the Merkle signature scheme, the result is the same but you would multiply k by the number of messages that can be signed. EG for 1 million $(2^{20})$ messages, the security level is $128-9-20=99$ bits.

The wikipedia article is about $F$ only: the "input" is one of the private keys, the "output" is the corresponding public key and "message digest size" is the output size of $F$. I think that it just attempts to say that when the private key is very short and regardless of the output size of $F$, it is trivial to find a preimage.


Bleichenbacher-attack test vectors I was trying to understand the Bleichenbacher-attack. I went through the paper of Bleichenbacher to understand it bit more. However I tried to get some test vectors to simulate this attack locally but couldn't find it.

Can some please help me in getting smaller test vectors so that I can do some hands on?

As mentioned by j.p., the original attack has been (quite significantly) improved in 2012 and some great tutorials are available online, often demonstrated with example.

If you want a more exhaustive list of test vectors, I suggest you take a look at Project Wycheproof, a tool developed by members of Google Security Team, designed to find vulnerabilities in cryptographic libraries. The idea behind this project is to use a large database of test vectors allowing to verify primitives conformance and check if they are vulnerable to some well known attacks.

You can find test vectors for RSA PKCS#1v1.5 for different key size (2048, 3072, 4096).

One of the maintainer of this project is Daniel Bleichenbacher himself (also Thai Duong, Emilia Kasper and Quan Nguyen), so test vectors should be valid!


Calculate share for a specific value of $x$ in Shamir's Secret Sharing scheme I am currently reading the book Cryptography: Theory and Practice (4th edition) by Stinson and Paterson and going through the exercises. I have reached the Threshold schemes section and am currently doing the exercises related to Shamir's secret sharing scheme.
The first exercise (11.8 in the 4th edition of the book) asks to write a computer program to compute a key starting from a list of shares, which I have done, and then test that the program computes the same key with different combinations of $x$ and $y$ values (which are provided in the exercise instructions), which I have also done.
Exercise 11.8 (b) then proceeds to ask the following:

Having determined the key, compute the share that would be given to a participant with x-coordinate equal to 10000. (Note that this can be done without computing the whole secret polynomial a(x).)

Perhaps I am misunderstanding the question, but my understanding is that the resulting $y = a(x)$ share does not depend on the $x$ value alone. Indeed, looking at the formula for computing a share:
$$a(x) = K + \sum_{j=1}^{t-1} a_jx_j \pmod p$$
(with $t$ the minimum number of shares required to reconstruct the key $K$)
we see that the final value of $a(x)$ will not only depend on the chosen $x$ values, but also from the chosen $a$ values. The values $a_1,...,a_n$ are also chosen by the dealer at the beginning of the key distribution process.
In light of all this, am I misunderstanding the exercise question or is it not possible to have a unique answer, unless you know all the $a_1,...,a_n$ values, which the exercise does not provide?
Or in other more concise words: am I supposed to have one and only one value for $a(10000)$?

In exercise 11.8, you have written a program that recovers the shared secret, that is, given $n$ pairs $x_i, y_i$ with $y_i = P(x_i)$ where $P$ is an unknown $n-1$ degree polynomial, evaluates $P(0)$.
Now, exercise 11.8b asks you to find the share with $x=10000$, that is, $y = P(10000)$ for the unknown polynomial $P$ that you have $n$ shares with already.
Here is one approach; define $P'(x) = P(x + 10000)$, and then trick your program into evaluating $P'(0)$.  The question then is "how do you find the $n$ pairs $x'_i, y'_i$ that satisifies $y'_i = P'(x'_i)$, using the $x_i, y_i$ pairs you have?".
I hope that is a enough of a hint...


Can I create a fixed length output from a fixed length input? I use AES256 for various purposes in my app. However, the purpose I am now trying to achieve is the following:

Input is for example AU00000001 and I would like a hashed or encrypted output of this with the same length (10 characters). I need to keep the output as small as possible, to convert it into a simple (minimal dots) QR code. And I do need the ability to reverse that output back to the original input.

I've read a few posts around here but I can’t find what I am looking for. Can you give me a hint or maybe point me to some references?

See “format-preserving encryption” at WikiPedia.

Depending on the size of the message space, one can get such a scheme by:

sorting pseudorandom values, see section 4.1 of “Format preserving encryption”,
or
using this arbitrary-size scheme described in “Perfect Block Ciphers With Small Blocks”,
or
using swap-or-not as described in “An Enciphering Scheme Based on a Card Shuffle”.

Nota bene: we also have a format-preserving tag that points to related questions and answers.


What does $\to$ mean in the following definition of a block cipher? In the following picture $\kappa$ is the key length and $n$ is the block size.

I understand that $\{0,1\}^\kappa$ means all possible combination of keys and $\{0,1\}^n$ means all possible combination of a plain-text block.

But I don't understand the overall equation, specially the meaning of the arrow $\to$. Can anyone explain it in brief? (note: I am very weak in mathematics)

  Let $E: \{0,1\}^\kappa \times \{0,1\}^n \to \{0,1\}^n$ be a block cipher with a $\kappa$ bit key and an $n$-bit state.

That definition is a standard definition which defines encryption as a function $E$. That function takes two inputs, a $\kappa$ bit key and a $n$ bit message.  Hence it is defined over the cartesian product - denoted as $\times$ - over these two sets, i.e. all bitstring of length $\kappa$ and $n$ respectively. It maps - denoted as $\rightarrow$ -  to an $n$ bit output (the ciphertext).


How secure is AES in a critical situation? So this one is a tinfoil-hat question.
It is 99 % theoretical.

So we assume that I am someone who stores highly confidential information. Maybe super secret stolen goverment stuff. And I get caught by the authorities.
The information is store in an AES256-XTS: Sha512 volume.
The attacker has unlimited money and power. Maybe a data-center.
So how long would it take to crack this and what would he attacks? The hash or the block cipher ?

PS: I know that AES was not chosen as standard because it is so secure, but because it has the best performance / hardware implementation / security balance. So maybe there are some AES backdoors in the implementation of some encryption-tools. So would it be better to use another algorithm in the case of highly sensitive data?

In practice, because they will target the easiest/weakest/least expensive link in the chain, they would attack you.

It is infinitely easier to threaten to crack someone's kneecaps to obtain their password then to crack an AES key.

Supposing they wanted to attack the cryptography specifically, for practice or fun, they would probably extract the key via a timing attack. This is not technically an attack on AES, it technically is an attack against a simple/common/fast implementation of AES. This is one of the few arguments I can think of for using an algorithm other then AES. Either that, or ensure that you utilize a constant time implementation of AES.

If your data is that confidential, then it is probably wise to utilize an algorithm that is not as vulnerable to leakage of information via side channels. Additionally, it's probably not safe to trust just software anymore: You would want a hardware security module.

Then, you need to become concerned with attacks against the hardware. You might opt for an algorithm that has been design with advanced counter-measures in mind, such as one based on the Keccak permutation.