[Library] SHA-256

[mctwist]

Killed due to the finickyness of torque and 32-bit plus arithmetic and my lack of an ability to make a proper bignum modulus function :'(
rip BLCrypto

I might be wrong, but didn't I made a modulus function that actually worked(And was pretty fast, too)? I wouldn't mind if you steal borrow it for your project. Otherwise, I could look into it again to make one that works.

[Ad Bot]

[Ipquarx]

I might be wrong, but didn't I made a modulus function that actually worked(And was pretty fast, too)? I wouldn't mind if you steal borrow it for your project. Otherwise, I could look into it again to make one that works.

If you did, I don't think I was ever notified of it... It's got to work on arbitrarily large numbers.

[mctwist]

If you did, I don't think I was ever notified of it... It's got to work on arbitrarily large numbers.

It's right there on this line.

Looking at it, I'm assuming it does not work as intended. But as I mentioned earlier, I might be able to make an another version, if you request for it.

[Pah1023]

It's right there on this line.

Looking at it, I'm assuming it does not work as intended. But as I mentioned earlier, I might be able to make an another version, if you request for it.

In your chr function ( for some stupid reason cloudflare is bitching about me including it in the post ), consider using collapseEscape("\\x" @ %n ).

[portify]

Consider not having a chr function at all if you're going for speed, and just look up the answer:

$chr0  ="\x00";
$chr1  ="\x01";$chr2  ="\x02";$chr3  ="\x03";$chr4  ="\x04";$chr5  ="\x05";
$chr6  ="\x06";$chr7  ="\x07";$chr8  ="\x08";$chr9  ="\x09";$chr10 ="\x0a";
$chr11 ="\x0b";$chr12 ="\x0c";$chr13 ="\x0d";$chr14 ="\x0e";$chr15 ="\x0f";
$chr16 ="\x10";$chr17 ="\x11";$chr18 ="\x12";$chr19 ="\x13";$chr20 ="\x14";
$chr21 ="\x15";$chr22 ="\x16";$chr23 ="\x17";$chr24 ="\x18";$chr25 ="\x19";
$chr26 ="\x1a";$chr27 ="\x1b";$chr28 ="\x1c";$chr29 ="\x1d";$chr30 ="\x1e";
$chr31 ="\x1f";$chr32 ="\x20";$chr33 ="\x21";$chr34 ="\x22";$chr35 ="\x23";
$chr36 ="\x24";$chr37 ="\x25";$chr38 ="\x26";$chr39 ="\x27";$chr40 ="\x28";
$chr41 ="\x29";$chr42 ="\x2a";$chr43 ="\x2b";$chr44 ="\x2c";$chr45 ="\x2d";
$chr46 ="\x2e";$chr47 ="\x2f";$chr48 ="\x30";$chr49 ="\x31";$chr50 ="\x32";
$chr51 ="\x33";$chr52 ="\x34";$chr53 ="\x35";$chr54 ="\x36";$chr55 ="\x37";
$chr56 ="\x38";$chr57 ="\x39";$chr58 ="\x3a";$chr59 ="\x3b";$chr60 ="\x3c";
$chr61 ="\x3d";$chr62 ="\x3e";$chr63 ="\x3f";$chr64 ="\x40";$chr65 ="\x41";
$chr66 ="\x42";$chr67 ="\x43";$chr68 ="\x44";$chr69 ="\x45";$chr70 ="\x46";
$chr71 ="\x47";$chr72 ="\x48";$chr73 ="\x49";$chr74 ="\x4a";$chr75 ="\x4b";
$chr76 ="\x4c";$chr77 ="\x4d";$chr78 ="\x4e";$chr79 ="\x4f";$chr80 ="\x50";
$chr81 ="\x51";$chr82 ="\x52";$chr83 ="\x53";$chr84 ="\x54";$chr85 ="\x55";
$chr86 ="\x56";$chr87 ="\x57";$chr88 ="\x58";$chr89 ="\x59";$chr90 ="\x5a";
$chr91 ="\x5b";$chr92 ="\x5c";$chr93 ="\x5d";$chr94 ="\x5e";$chr95 ="\x5f";
$chr96 ="\x60";$chr97 ="\x61";$chr98 ="\x62";$chr99 ="\x63";$chr100="\x64";
$chr101="\x65";$chr102="\x66";$chr103="\x67";$chr104="\x68";$chr105="\x69";
$chr106="\x6a";$chr107="\x6b";$chr108="\x6c";$chr109="\x6d";$chr110="\x6e";
$chr111="\x6f";$chr112="\x70";$chr113="\x71";$chr114="\x72";$chr115="\x73";
$chr116="\x74";$chr117="\x75";$chr118="\x76";$chr119="\x77";$chr120="\x78";
$chr121="\x79";$chr122="\x7a";$chr123="\x7b";$chr124="\x7c";$chr125="\x7d";
$chr126="\x7e";$chr127="\x7f";$chr128="\x80";$chr129="\x81";$chr130="\x82";
$chr131="\x83";$chr132="\x84";$chr133="\x85";$chr134="\x86";$chr135="\x87";
$chr136="\x88";$chr137="\x89";$chr138="\x8a";$chr139="\x8b";$chr140="\x8c";
$chr141="\x8d";$chr142="\x8e";$chr143="\x8f";$chr144="\x90";$chr145="\x91";
$chr146="\x92";$chr147="\x93";$chr148="\x94";$chr149="\x95";$chr150="\x96";
$chr151="\x97";$chr152="\x98";$chr153="\x99";$chr154="\x9a";$chr155="\x9b";
$chr156="\x9c";$chr157="\x9d";$chr158="\x9e";$chr159="\x9f";$chr160="\xa0";
$chr161="\xa1";$chr162="\xa2";$chr163="\xa3";$chr164="\xa4";$chr165="\xa5";
$chr166="\xa6";$chr167="\xa7";$chr168="\xa8";$chr169="\xa9";$chr170="\xaa";
$chr171="\xab";$chr172="\xac";$chr173="\xad";$chr174="\xae";$chr175="\xaf";
$chr176="\xb0";$chr177="\xb1";$chr178="\xb2";$chr179="\xb3";$chr180="\xb4";
$chr181="\xb5";$chr182="\xb6";$chr183="\xb7";$chr184="\xb8";$chr185="\xb9";
$chr186="\xba";$chr187="\xbb";$chr188="\xbc";$chr189="\xbd";$chr190="\xbe";
$chr191="\xbf";$chr192="\xc0";$chr193="\xc1";$chr194="\xc2";$chr195="\xc3";
$chr196="\xc4";$chr197="\xc5";$chr198="\xc6";$chr199="\xc7";$chr200="\xc8";
$chr201="\xc9";$chr202="\xca";$chr203="\xcb";$chr204="\xcc";$chr205="\xcd";
$chr206="\xce";$chr207="\xcf";$chr208="\xd0";$chr209="\xd1";$chr210="\xd2";
$chr211="\xd3";$chr212="\xd4";$chr213="\xd5";$chr214="\xd6";$chr215="\xd7";
$chr216="\xd8";$chr217="\xd9";$chr218="\xda";$chr219="\xdb";$chr220="\xdc";
$chr221="\xdd";$chr222="\xde";$chr223="\xdf";$chr224="\xe0";$chr225="\xe1";
$chr226="\xe2";$chr227="\xe3";$chr228="\xe4";$chr229="\xe5";$chr230="\xe6";
$chr231="\xe7";$chr232="\xe8";$chr233="\xe9";$chr234="\xea";$chr235="\xeb";
$chr236="\xec";$chr237="\xed";$chr238="\xee";$chr239="\xef";$chr240="\xf0";
$chr241="\xf1";$chr242="\xf2";$chr243="\xf3";$chr244="\xf4";$chr245="\xf5";
$chr246="\xf6";$chr247="\xf7";$chr248="\xf8";$chr249="\xf9";$chr250="\xfa";
$chr251="\xfb";$chr252="\xfc";$chr253="\xfd";$chr254="\xfe";$chr255="\xff";

$chr[%n]

[mctwist]

In your chr function ( for some stupid reason cloudflare is bitching about me including it in the post ), consider using collapseEscape("\\x" @ %n ).

Consider not having a chr function at all if you're going for speed, and just look up the answer:

-snip-

Yeah, you're both right. However, I just threw this library together as a proof of concept. It was never intended to be optimal or perfect. It's funny when people in the encryption thread uses it as a comparison for their benchmarks. It's even funnier that few of them remarked on the fact that I was the only one with a working division operator.

I could go through it some other time and improve its performance and fix bugs. Also, why not add support for fixed floating point?

Edit: Didn't you actually came pretty far? Or did I miss something in that conversation?

[Ipquarx]

It's right there on this line.

Looking at it, I'm assuming it does not work as intended. But as I mentioned earlier, I might be able to make an another version, if you request for it.

This does seem like it would work, but only if %a never goes out of the range of the 31 bits of unsigned space that integers have. It won't work for cryptography purposes because the modulus needs to be on the order of 256 bits, not 30-31.

I also considered this general approach (Adding a single "digit" at a time then getting the modulus again) right from the start, the problem is if you're adding one bit at a time and then doing a subtraction operation for every bit, it gets real slow real fast. The method that I had planned would do the equivalent of 3 addition/subtraction operations for every 16 bits, which is 5.3x faster, but I couldn't ever get it working. I did get pretty close to completing it and I can outline the general idea if you want.

[Meldaril]

Is that the right-to-left binary method?

[mctwist]

This does seem like it would work, but only if %a never goes out of the range of the 31 bits of unsigned space that integers have. It won't work for cryptography purposes because the modulus needs to be on the order of 256 bits, not 30-31.

I also considered this general approach (Adding a single "digit" at a time then getting the modulus again) right from the start, the problem is if you're adding one bit at a time and then doing a subtraction operation for every bit, it gets real slow real fast. The method that I had planned would do the equivalent of 3 addition/subtraction operations for every 16 bits, which is 5.3x faster, but I couldn't ever get it working. I did get pretty close to completing it and I can outline the general idea if you want.

Hm, I think I didn't read my own implementation completely right. It works only if %a, as you say, goes out of 31 bits. This may happen for very large numbers or, in some rare obscure reason, for large primes. I think there's a faster way to calculate modulus for larger number, but I just cannot remember it right now.

Also, for power of for integer, I found this not long time ago: http://stackoverflow.com/a/101613. I could try to implement that to boost my Math::pow as well. It even says there that that is the default algorithm for the encryption you guys were working on.

[mctwist]

Time to revive this thread with an addition from my part. I managed to make a more optimized version of the binary addition that was inlined into this function.

I've tested it several times on different values, and I did not find any issues with it so far. I even checked against several hashes to make sure that it worked as intended.

Benchmark:
Running sha1("") 999999 times: 1408 ms, or ~1.4 µs per call
Running Port's sha256("") 9999 times: 74384 ms, or ~7.4 ms per call
Running McTwist's sha256("") 9999 times: 44368 ms, or ~4.4 ms per call

This makes it roughly 40% faster than previous version.