mercredi, février 20, 2019

ECC backdoors for dummies in 5 steps

It will be explained in the most simple and pragmatic way, what possible ECC backdoors look like and why choosing the right curve and the right prime number to build the cryptographic curve is important.

1st step: understand how ecc cryptography works

Read and meditate

2nd step: Understand graphically how a scalar multiplication looks like when choosing the right base point with a good prime number on a good curve 

We first takes a random base point (2,22) and scalar multiply from 1 to n until it reaches infinity or point (0,0), then we look for the next base point that was not part of previous loop and multiply it, and so on until there are no free untouched base points.

For [y2 = x3 + 0x + 7  Ordre 67  size 78] curve whatever base point you start with, the loop contains all points of the curve (plus(0,0)), Thus there is only one curve.

To decrypt some data, without knowing the key, using these parameters you have to do 78 tests.

3rd step: choose a wrong prime number on a good curve

We first takes a random base point (1,9) and scalr multiply from 1 to n until it reaches infinity or point (0,0), then we look for the next base point that was not part of previous loop (6,2) and multiply it, and so on until there are no free untouched base points.

For [y2 = x3 + 0x + 7  Ordre 73  size 63] curve, loop sizes are 8 or 4.  

To decrypt some data, without knowing the key, using these parameters you have to do only a maximum of 8 tests.

What makes the [y2 = x3 + 0x + 7  Ordre 73  size 63] curve a bad choice is that at least one base point is on the x axis here zero_base_points are (42,0), (44,0) & (60,0)

4th step: choose a wrong curve

Some curves do not show any prime number without any zero_base_points:

(y2 = x3 + 0x + 1,TreeSet())
(y2 = x3 + 0x + 2,TreeSet(13, 37, 67, 139, 379, 541))
(y2 = x3 + 0x + 3,TreeSet(7, 31, 43, 79, 163, 199, 223, 463))
(y2 = x3 + 0x + 4,TreeSet())
(y2 = x3 + 0x + 5,TreeSet(43, 73, 193, 223, 277, 307, 397, 433))
(y2 = x3 + 0x + 6,TreeSet(31, 199, 223, 271, 367))
(y2 = x3 + 0x + 7,TreeSet(67, 229, 241, 499))
(y2 = x3 + 0x + 8,TreeSet())

5th step: going further open points

The code to draw these curves :

lundi, juin 24, 2013

How bitcoin may be already crumbling under its own success

The bitcoin community has recently discussed about government interference, but today, I want to discuss 2 mostly overlooked bitcoin news:
 * blockchain has reached a size of 8 Gb
 * transactions shall have, now, a minimum size

 These 2 events/news are closely related. Every transaction contributes to the 8Gb ledger size, and "they (the miners?)" want to limit the ledger size. This will be done by fighting transaction spam i.e. eliminating insignifiant exchanges and non-financial transactions such as those initiated by satoshidice.

Why is it needed to limit transactions when there are so few users?
Is limiting transactions today a sign that bitcoin will not scale well?

Some predict that bitcoin market capitalization will reach orders tens, hundred of billions or even trillions.
 * How many people will use bitcoins in a few years?
 * What will be, then, the size of the bitcoin ledger? Will it still be manageable? 

Most probably to keep the ledger at a computable size, transaction size will be limited to higher limits. People will be less able to use it, then, for day to day transactions, if the limit is set to 0.1 bitcoin (equivalent to 100$?) for instance.

Maybe are we going to need to use other currencies, for smaller amounts, such as litecoin sometimes deemed as "silver compared to bitcoin's gold"? If "open currencies" become mainstream, I guess in addition to gold and silver, copper, iron, lead and feather coins are going to be needed to be able to manage the huge number of transactions when half the planet is going to use these new currencies.

Today's amount of transfers is looking like ripples compared to tomorrow's tsunamis of transactions. If we consider bitcoin as the "Napster" of open currencies and expect future open currencies, answering to those questions, which I personnally find unsolved yet, is something essential.

Or ... did I miss something?
A few weeks ago, I understood that maybe oldest parts of the ledger will be dropped. When will that happen?

 Anyway the amount of transactions is already a problem because today  "they" feel they should limit the number of transactions.

vendredi, novembre 02, 2012

Managing dates with a DSL implemented in Scala

Following Paulo "JCranky" Siqueira's post who himself built it based on Sergio Lopes's post, I also enhanced this class by adding the ability to set dates and to compare them.

Another good link: Baysick: A Scala DSL Implementing BASIC

package kebra

import java.util.Calendar
import java.text.SimpleDateFormat
import java.text.ParsePosition

class DateDSL(val cal: Calendar) {
 import DateDSL.Conjunction
 def this(d: DateDSL) = this(

 private var last = 0;

 def plus(num: Int) = { last = num; this }
 def minus(num: Int) = { last = -num; this }

 def +(num: Int) = plus(num)
 def -(num: Int) = minus(num)

 def months = { cal.add(Calendar.MONTH, last); this }
 def months(and: Conjunction): DateDSL = months
 def month = months
 def month(and: Conjunction): DateDSL = months

 def years = { cal.add(Calendar.YEAR, last); this }
 def years(and: Conjunction): DateDSL = years
 def year = years
 def year(and: Conjunction): DateDSL = years

 def days = { cal.add(Calendar.DAY_OF_MONTH, last); this }
 def days(and: Conjunction): DateDSL = days
 def day = days
 def day(and: Conjunction): DateDSL = days

 def is(then: Calendar) = {

 def is(then: String) = {
  val cthen = ParseDate(then,"MM/dd/yyyy")

 def ParseDate(s_date: String, s_format: String): Calendar = {
  var cal = Calendar.getInstance()
  cal.setTime(new SimpleDateFormat(s_format).parse(s_date, new ParsePosition(0)))

 def before(d: DateDSL): Boolean = cal.before(
 def after(d: DateDSL): Boolean = cal.after(

 override def toString = new String(new SimpleDateFormat("ddMMMyy").format(cal.getTime()))

object DateDSL {
 class Conjunction
 val and = new Conjunction

 def Today = new DateDSL(Calendar.getInstance)
 def Tomorrow = Today + 1 day
 def Yesterday = Today - 1 day

 def today = Today
 def tomorrow = Tomorrow
 def yesterday = Yesterday

 def Now = Today
 def now = Today
I also added a testcase below:
package kebra

import java.util.Calendar
import java.text.SimpleDateFormat
import kebra.DateDSL._

object TestKebra extends App {

 println("Hello World!")
 println(Tomorrow minus 1 month and plus 10 years and plus 1 day)
 println(Today + 2 months and plus 9 years and minus 1 day)
 println(Today - 9 years and minus 1 day)
 println(((Today + 2 months and) + 9 years and) - 1 day)
 println(now is "10/1/2011" plus 3 days)
 println("\n"+printZisday((now is "10/1/2011" plus 3 days).cal,"ddMMMyy"))
 assert(printZisday((now is "10/1/2011" plus 3 days).cal,"MM/dd/yyyy").indexOf("10/04/2011")==0)
 assert((now is "10/1/2011" plus 3 days).before(now is "10/1/2011" plus 4 days))
 assert((now is "10/1/2011" plus 4 days).after(now is "10/2/2011" plus 2 days))
 val zendDate = new DateDSL(now is "2/2/2011")
 var ago = new DateDSL(now is "2/2/2011" minus (9*7) days)
 println("***** ago: "+ago+", zendDate: "+zendDate)
 while(ago.before(zendDate)) {
  println("      ago: "+ago)
  ago plus 7 days
 println("***** ago: "+ago+", zendDate: "+zendDate)
 assert((ago plus 1 day).after(zendDate))
 println("***** ago: "+ago+", zendDate: "+zendDate)
 assert((ago minus 2 days).before(zendDate))
 println("***** ago: "+ago+", zendDate: "+zendDate)
 def printZisday(zisday:  Calendar, fmt: String): String = new String(new SimpleDateFormat(fmt).format(zisday.getTime()))

jeudi, décembre 08, 2011

Simple linear regression in Scala

Here is how to compute Simple linear regression in Scala.
Class LinearRegression takes in n measurements from a List[(x: Double, y: Double)] and computes the line that best fits the data according to the least squares metric.
This Scala program is the scala translation of the java program available at .
class LinearRegression(val pairs: List[(Double,Double)]) { 
 val size = pairs.size
 println("pairs = " + pairs)

 // first pass: read in data, compute xbar and ybar
 val sums = pairs.foldLeft(new X_X2_Y(0D,0D,0D))(_ + new X_X2_Y(_))
 val bars = (sums.x / size, sums.y / size)

 // second pass: compute summary statistics
 val sumstats = pairs.foldLeft(new X2_Y2_XY(0D,0D,0D))(_ + new X2_Y2_XY(_, bars))

 val beta1 = sumstats.xy / sumstats.x2
 val beta0 = bars._2 - (beta1 * bars._1)
 val betas = (beta0, beta1)

 println("y = " + ("%4.3f" format beta1) + " * x + " + ("%4.3f" format beta0))

 // analyze results
 val correlation = pairs.foldLeft(new RSS_SSR(0D,0D))(_ +, bars, betas))
 val R2 = correlation.ssr / sumstats.y2
 val svar = correlation.rss / (size - 2)
 val svar1 = svar / sumstats.x2
 val svar0 = ( svar / size ) + ( bars._1 * bars._1 * svar1)
 val svar0bis = svar * sums.x2 / (size * sumstats.x2)
 println("R^2                 = " + R2)
 println("std error of beta_1 = " + Math.sqrt(svar1))
 println("std error of beta_0 = " + Math.sqrt(svar0))
 println("std error of beta_0 = " + Math.sqrt(svar0bis))
 println("SSTO = " + sumstats.y2)
 println("SSE  = " + correlation.rss)
 println("SSR  = " + correlation.ssr)

object RSS_SSR {
 def build(p: (Double,Double), bars: (Double,Double), betas: (Double,Double)): RSS_SSR = {
  val fit = (betas._2 * p._1) + betas._1
  val rss = (fit-p._2) * (fit-p._2)
  val ssr = (fit-bars._2) * (fit-bars._2)
  new RSS_SSR(rss, ssr)

class RSS_SSR(val rss: Double, val ssr: Double) {
 def +(p: RSS_SSR): RSS_SSR = new RSS_SSR(rss+p.rss, ssr+p.ssr)

class X_X2_Y(val x: Double, val x2: Double, val y: Double) {
 def this(p: (Double,Double)) = this(p._1, p._1*p._1, p._2)
 def +(p: X_X2_Y): X_X2_Y = new X_X2_Y(x+p.x,x2+p.x2,y+p.y)

class X2_Y2_XY(val x2: Double, val y2: Double, val xy: Double) {
 def this(p: (Double,Double), bars: (Double,Double)) = this((p._1-bars._1)*(p._1-bars._1), (p._2-bars._2)*(p._2-bars._2),(p._1-bars._1)*(p._2-bars._2))
 def +(p: X2_Y2_XY): X2_Y2_XY = new X2_Y2_XY(x2+p.x2,y2+p.y2,xy+p.xy)