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

Bitcoin Basics

When a Bitcoin Wallet Program synchronizes its own list of Receiving Addresses, it broadcasts a query over the network, which names each Public Key / Address, and the network replies with an updated history, of whether that Address has Sent or Received any funds since the last sync, on the assumption that the same Bitcoin Wallet also stores the corresponding Private Keys. If the Wallet Program tries to Send any funds From one of its Addresses, it must Prove that it holds the Private Key, by Signing the request to do so, using Public Key Cryptography. This signature can be verified by anybody using only the Public Key.

If the stated Address has never received any funds, I believe that the query disappears from the network within some short amount of time.

It is common practice in Public Key Cryptography, additionally to encrypt any Private Keys using a Password which is not stored, and which the user must enter, every time he wants to use them, but not to encrypt the Public Keys. Since simply to receive an update for the Public Keys does not require the user enter his Password, it follows that the Wallet Program does not need to prove to the network, that it does have the Private Keys stored.

Otherwise, if the Wallet stores any Public Keys without the corresponding Private Key, by default, those are assumed to belong to other users, as potential Addresses to Send funds to. And this is about as much as a basic Bitcoin Wallet Program needs to be able to do.

However, most specific Wallet Programs have additional features and capabilities, specific to one Program. For example, some Wallet Programs allow for more than one Wallet to be created, and additionally allow for pure, Address-Watching Wallets to be created, which when synced, also query the network for a list of Addresses, but for which the Wallet in question does not store any Private Keys. These Wallets receive updates for the list of Addresses even though the Addresses in question are actually externally-owned, since the network never required any proof from the Program anyway, that it has the Private Keys.

I think the main disadvantage of this approach, is the fact that this separate Wallet does not get synced, unless the user specifically instructs his Program to Open that one.

But, since some programmers do not feel that their users need these advanced capabilities, certain Wallet Programs simply leave them out, especially in the case of Wallets meant for smart-phones. OTOH, smart-phone Wallets often have additional capabilities, related to being able to scan QR-codes, in order to acquire Addresses to Send To, or to acquire ‘Requests For Funds’, which in addition an Address, contain the Amount that should be Sent, within the same QR-code…

Dirk

 

An Interesting Tool for creating Paper Wallets

I have written various postings now, about Bitcoin Wallets. One of the themes which I have brought up, is that the online account, of how much money has been Sent To and From a Bitcoin Address, is more important, than the offline account of it, which can therefore sometimes be reduced to only a Private Key and a Public Key. The Public Key can be converted to and from a Bitcoin Address to Send funds To, while the Private Key can be used to authorize, that funds be Sent From the same Address.

And so one subject which I also wrote about, is that if a person has the Private Key, he or she can use some existing Bitcoin Wallet apps, to Sweep that Address, thus giving the command to the network, to Send all its funds to another Address, which is online.

There is some minor discrepancy, between what I called an ‘Offline Wallet’, and what the Internet calls an “Offline Wallet”. What I was referring to by that term, would actually be called “A Wallet In Cold Storage”. What the Internet may refer to instead, is a kind of Wallet, being accessed by a program, but on a computer which is separated from the Internet by an Air Gap.

In reality, the subject of the security of Air Gap systems, is quite beyond what I am currently willing to write about. My personal guess is, that if most of us wanted that, we might be a bit too paranoid for the mundane world. There exist some organizations and even companies, who need Air Gap Systems, but then there is a whole rigamarole, of what needs to be done, for an Air Gap system actually to receive the full benefit, one hopes to gain by using them…

But, having done some reading, I have come across a tool which even everyday users could find useful, in creating an actual Paper Wallet:

Online Tool

Because all that is needed for one Bitcoin Address to exist, in principle, is a correctly-formatted set of Private and Public Keys, a tool can be useful somewhat, which only does that, and which offers to print those out as QR Codes. The above Link is a Web-page, which does this.

(Edit 10/08/2016 : Actually, I had previously posted a mistake here. As it stands, if a person transfers a Bitcoin-amount to an Address that is validly-formed, that amount will remain associated with the Address, even if no attempt is made to query the Address. This Bulletin-Board Conversation seems to state so.)

Continue reading An Interesting Tool for creating Paper Wallets