Threshold Encryption

One concept which fascinates me, is Public Key Cryptography, of which RSA encryption was the earliest, strong example. But a variant of public-key cryptography which exists, and which I have not paid much attention to, is Threshold Encryption. The WiKi Article states that it exists, but does not explain how it would work. There could be more than one way to accomplish threshold encryption, but I can think of one that will work. As its basis, my own, hypothetical system would have the assumption, that a certain author for an encrypted message, intends for two specific recipients to be able to decrypt that message, but only if both recipients apply their keys. The communication of the recipients’ keys could be a secure communication from the author, which could itself be accomplished using public-key, single-recipient, cryptography.

This basis has the following assumptions:

  • The encryption of the message could take place, by raising the message to a public-key exponent (E), such as again, 65537, in the modulus of (p)(q), where (p) and (q) are prime numbers.
  • Each recipient would possess a private exponent (d1 or d2), but possess none out of (p), (q), (p-1), or (q-1) by itself. Instead, everybody would know the public-key modulus (p)(q), on the assumption that it cannot be prime-factorized into (p) and/or (q).
  • (The author would compute two multiplicative inverses of 65537, one in the modulus of (p-1), and the other in the modulus of (q-1), hence calling these smaller exponents (d1) and (d2), ? )
  • If the two recipients need to decrypt the message, they could perform a simple, integer multiplication of their individual, private exponents, to arrive at (D = (d1)(d2)), which should then also become the multiplicative inverse of 65537 in the modulus (p-1)(q-1).
  • Raising the cyphertext to the exponent (D) in the modulus (p)(q) will undo the encryption as with ordinary, RSA-encryption.
  • Even if I was mistaken in how exactly (d1) and (d2) are computed, as an alternative to multiplying them, the recipients can apply them sequentially, as exponents in the modulus of (p)(q), so that the end result is to decrypt the original message.

But I see a major shortcoming of this approach. I see no way in which both recipients could generate their own private exponents, and to communicate the corresponding public key to the author, supposedly securely over an insecure channel. The reason for this would be the fact that both recipients would need to be aware of the same modulus, as well as of one of the prime numbers used. Simple division of the modulus by either prime number will reveal the other, and thus break the encryption. Even to know (p-1) for example, will trivially reveal (p), and therefore also reveal (q).

But, the same math could be extended such, that three recipients need to supply their individual private keys (d1, d2 and d3), if the public-key modulus was instead (p1)(p2)(p3)…

But then the question would need to exist separately, as to what would happen if there needed to be (n) potential recipients, any (t) out of which are required to decrypt a message. The only solution which I could see, would be to base that on hybrid encryption, where a symmetrical key would be encrypted multiple times, each time to a subset of (t) recipients out of the larger set (n). Each subset of recipients would need to decrypt the symmetrical key, as created with a different modulus.

(Updated 09/21/2018, 19h30 : )

Continue reading Threshold Encryption

SegWit versus Bitcoin Unlimited

In the operation of Bitcoin, there is a crisis brewing. Bitcoin mining pools are restricted by a feedback-control loop which they defined, in the days of the inception of Bitcoin, only to be able to “mine” 1 Block every 10 minutes, which is inserted into the block-chain when that has been achieved, and which acts as a slate, onto which all Bitcoin transactions must be recorded. A block currently occupies 1MB of data, and the size of individual transactions to be recorded in it, can vary greatly, but averages 500 Bytes for the simplest types of transactions.

What this means, is that 1 Block can typically hold 2000 transactions, but will only be mined every 600 seconds, on the average, so that a global rate of available transactions of 3 /second would seem to follow. Because the world that uses Bitcoin is presently trying to conduct transactions at a faster pace – because in some parts of the world, Bitcoin is a currency – there have sometimes been escalations in the transaction fees, which are charged according to how many KB of one block the transaction consumes. Recently, the transaction fees were around 2 milliBits/kB, or 0.002 BTC/kB. That counts as extremely expensive, since 1 BTC is approximately worth CAD 2000 right now, meaning that the transaction fee could be around CAD 1.- . Many items and services people might want to buy, would not cost much more than the CAD 1.- of my country’s real currency.

Bitcoin operators recognize that a problem exists, and there exist two camps who are in conflict right now, over what to do about it:

  1. Bitcoin Unlimited
  2. Bitcoin Core

Out of these two groups, Bitcoin Core represents the status quo.

What Bitcoin Unlimited is proposing, sounds straightforward: Increase the block-size, and allow for it to be increased again, as the demand for transactions increases in the future. But there are some problems with what Bitcoin Unlimited is proposing. Changing the format of the blocks, and/or the protocol, would essentially create two types of currencies:

  • The legacy currency, which might be referred to as BTC -units, and
  • A new form of Bitcoins, which might be referred to as XBT -units.

If one mining pool was unilaterally to adopt a new Bitcoin block-format, this would be called a ‘Hard Fork’. In the event of a hard fork, people who held Bitcoin-amounts on the legacy block-chain, would see that that legacy block-chain has been imported into both newly-forming block-chains. Wallet-holders would therefore see, that they have a double-dipping; they’d have their present amounts both as BTC and as XBT. But, if they were to mix their Bitcoins into a new block, using a type of transaction that has more than one input, those Bitcoin-amounts would become invalid on the other, newly-differing chain.

There would be a bigger problem in the event of a hard fork, which is known as the risk of a Replay Attack. Because the legacy chain was not designed with the possibility of two future continuations in mind, after a hard fork, if a wallet-holder was to pay for a service in, say, XBT, then the payee – or somebody else – would be able to use the credentials the wallet-holder used in his own transactions, which worked for XBT, and could replay those transactions – actually signing the same inputs as before surreptitiously – but this time, pay out the amounts to another public address, as a BTC -amount. So the payer would see both his XBT and his BTC coins disappear, while only having authorized one of the two transactions himself, out of the legacy-chain.

As an alternative to a hard fork, Bitcoin Core is proposing a short-term solution named “SegWit”. This is a proposed solution, that will cause fewer bytes of data to be written to the block, per transaction, and which it is hoped, will allow the increased number of transactions to be served, that the world is asking for right this instant.

This is a video, which describes in storybook-form, what SegWit proposes. Essentially, a Bitcoin transaction possesses a list of inputs, and a list of outputs. No public address really owns the transaction, but the transaction proposes to use unspent outputs, made to the person who holds the private key, for the public key the outputs were made to – that constitute his Bitcoin balance – as an input or as inputs, and to state somebody else’s public address as the recipient of the outputs.

What Bitcoin experts know, is that the inputs-list of a transaction takes up much more space, on average, than the outputs list does. The reason for this, is the fact that in order to specify an input, Bitcoin is so restrictive, that one specific output must be identified, and not just one public address, to which the output was received. This means, that the complete Transaction ID must be stated in the inputs-list, as well as the sequence-number, the position of the output received, in the outputs-list, of the specified transaction, so that the current wallet-holder can use it as an input. This is expensive in the number of bytes used, because in addition to that, the public key of the recipient must be embedded in the inputs-list, as well as the signature with which the holder of the public address authorized the received output be unlocked.

  1. Transaction ID : 32 + 4 Bytes
  2. Sequence Number : 4 Bytes
  3. Public Key : 33 or 65 Bytes
  4. Signature : ~72 Bytes
  5. Additional Bytes used for script-instructions: (?)

But there is an added twist to how Bitcoin works. We might expect that this information is simply entered by software, into fields that belong to a transaction with a specific syntax. But as it stands, only the fields (1) and (2) above exist statically in a transaction. The rest is embedded as literal constants, in a very scaled-down forth-like language called “Script“.

The way script works in general, is that the piece of script in the inputs-list of the recipient, is executed before the piece of script in the outputs-list of the sender. The script of the output defines the conditions that need to be met, in order for the recipient – in another transaction than the transaction that states this script as an output – to be able to claim the amount. In order to satisfy those conditions, the script of the recipient – in his inputs-list – leaves a number of objects on a stack, which the script in the outputs-list of the sender can use as input.

According to the way Bitcoin has traditionally worked then, was that the input defined by the recipient, would place his public-key, and his signature onto the stack, in expectation that this is what the output of the sender requires. The input does this in the form of an embedded public key, and an embedded signature, in its actual script, which were placed there by software running normally on computers, and not running through script.

But the output script of the sender would then expect these data to be on the stack in a predefined order, and would verify that two conditions were met:

  1. When hashed, the public-key must equal the public address of the intended recipient (Those are not really the same thing), ( :1 )
  2. The signature must be decrypted by the same public key, to equal a hash of the transaction being claimed as input.

In order for the outputs-script to verify this, it must also receive the Transaction ID of the transaction it belongs to on the stack, but this is not the responsibility of the inputs-script of the recipient to place there.

What SegWit proposes, is that the inputs-script should neither need to state the public key of the recipient anymore, nor his actual signature, thus making the transaction shorter. Thereby, something needs to signal, that this public key should be taken ‘from the side’, from the “Extended Block”, but fed to an established output script.

While this is all very fascinating, it reveals two very serious problems of its own:

Continue reading SegWit versus Bitcoin Unlimited

Finding the Multiplicative Inverse within a Modulus

The general concept in RSA Cryptography is, there exists a product of two prime numbers, call them (p) and (q), such that

(T ^ E) ^ D mod (p)(q) = T

where,

T is an original plaintext document,

E is an encryption key,

D is the corresponding decryption key,

E and D are successively-applied exponents, of T,

(p)(q) is the original modulus.

A famous Mathematician named Euler found, that in order for exponent operations on T to be consistent in the modulus (p)(q), the exponents’ product itself must be consistent in the modulus (p-1)(q-1). This latter value is also known as Euler’s Totient Product of (p)(q).


 

There is a little trick to this form of encryption, which I do not see explained often, but which is important. Since E is also the public key, a relatively small prime number is used in practice, that being (2^16 + 1), or 65537. D could be a 2048 or a 4096-bit exponent. The public key consists of the exponent E and the modulus (p)(q) packaged together.

Thus, when the key-pair is created, (p) and (q) must be known separately, so that D can be computed, and then (p-1)(q-1), which hopefully never touched the hard-drive, can be discarded, after D is saved, along with (p)(q) again, this time forming the private key.

Therefore, D must be the multiplicative inverse of E, in the modulus of (p-1)(q-1). But how does one compute that?

Continue reading Finding the Multiplicative Inverse within a Modulus

Opus En Ligne

( Last edited on 11/25/2016. )

On the Island Of Montreal, bus and subway fares have been handled for many years via a contact-less smart-card, called our “Opus Card”. Most residents “recharge” their fares at designated commercial establishments, but those so inclined may instead buy a USB-connected reader for this card, which also has contacts, which the privately-used readers use to recharge them.

I am one passenger, who chooses to pay their fares this way at home, by plugging the USB-cable of the card-reader into my remaining Windows 7 computer named ‘Mithral’, and by going to a Web-site, where we can provide payment information.

Until last month, the way in which this system worked was:

  • We install a device-driver for the actual card reader – which is chosen for us by the designated site.
  • We kept our Java installation up-to-date.
  • The site charges our payment method, validated on their side.
  • The Web-site deployed and launched a Java application with each use, that connected to the card reader and wrote changes to the data on the card.

At least in theory it was possible to say, that this system was based on an open standard, that being Java.

But as of this month, the transit authority has switched to a different system. We still need the actual USB driver for the card reader. But now we must also download what they call their ‘SmartCardPlugin’, which is given to us from the site as an .MSI File in the case of Windows users. This plug-in actually forms the bridge, between their Web-application and the recognized card reader.

While this system seems to work quite well, based on my first use today, I would say it represents bad programming aesthetics. Even though the actual software-components were provided by Xerox, this system does not install a PKCS#11 security device, nor anything approaching a CAC card reader, with PKI. Instead, this service is based on an .EXE File, and leaves its hook in our browser, which in the case of Firefox, we can find under Tools -> Options -> Applications.

What this means is that the site will display an Web-object, that needs to be ‘opened’ by a specific application, associated by the Web-browser.

The most positive aspect to how this works seems to be, that indeed, it provides compatibility with Firefox, Chrome, IE etc..

But instead of providing strong security, this method is only as secure as the SSL connection to the site.

It may be interesting to note, that even when this system was based on Java, none of the officials ever promised that it would work under Linux, so I see no loss there.

Some users have complained, in that this system fails to meet their expectations, in one day combining the payment service as a smart-phone, NFC service. I have to concur with this hope. I also find it a bit clumsy right now, to have to plug in my Opus Card into a USB port, and to open a site which asks me for my payment credentials – ‘the old-fashioned way’.

But OTOH, I do not see much of a practical loss, compared with how it used to work. And one reason the officials may be doing it this way, could be a negative prognosis for the future of Java itself.

It just so happens that I prefer proven standards.

Dirk

Continue reading Opus En Ligne