ImageSteganography

SRM 225 · 2004-12-28 · by Kawigi

SRM 225 · 2004-12-28 · by Kawigi · Encryption/Compression, Simple Math, String Manipulation

Show categories

Class Name: ImageSteganography

Return Type: String[]

Method Name: encode

Arg Types: (vector<string>, string)

Problem Statement

Steganography is a method of cryptography where a message or entire document can be hidden inside of another file or image which shows no evidence that there is data hidden in it. Typically, the message or document to be sent is first encrypted and compressed, and then combined with an existing file in the bits that are less significant.

For example, the encrypted, compressed file could be combined with a bitmap image, and each byte of the file could be encrypted into the lowest two bits of 4 pixel values. The result would be that there is a 1/4 chance that a given pixel is completely unchanged, and a 3/4 chance that it is changed, but by such a small amount that it is essentially undetectable.

While it is not as secure or efficient, you could quite easily encrypt a message into a bitmap image with no encryption or compression, and your message would be protected by the fact that the image has no distinguishable traits that suggest that a message is hidden in it. You will be given an "image" and you will encode a given message into it and return the new image. The returned image should be in the same format as the original image.

The image will be in the format of a String[] where each three digits represent a number from 0 to 255, inclusive (leading zeros will be added as necessary), which is a pixel value in the image. You will also be given a String, message which contains the message you would like to encode into the image. You will first encode the message into numbers representing the characters in the message - spaces will be 0, 'A'-'Z' will be 1-26, 'a'-'z' will be 27-52, '0'-'9' will be 53-62, and 63 will be used for any space after the message. All these numbers can be represented in binary with 6 digits. You will put each pair of bits (representing a number between 0 and 3) into the lowest two bits of the values in the image. For each character, you will put in the lowest two bits, then the middle two, then the highest two, and then continue to the next character. You will put them in the lowest two bits of the first pixel on the first row, then the second pixel on the first row, and so on until you get to the end of the first row, then the first pixel on the second row, and so on. Once you are out of characters, continue substituting the lowest two bits of each pixel value as if the current character were represented by number 63.

Notes

The number of pixels in image may not be a multiple of 3, but you should continue inserting the message as if there was room to finish the last character.

Constraints

image will have between 1 and 50 elements, inclusive.
The number of characters in each element of image will be a multiple of 3 between 3 and 48, inclusive.
message will have between 1 and 50 characters, inclusive.
There will be enough room in image to encode message.
Each element of image will be made up of 3-digit numbers between 0 and 255, inclusive, padded with zeros if necessary.
The characters in message will be spaces, numbers, and upper- and lower-case letters.

Examples

{"255123212001201222"}
"hi"
Returns: { "254120214003200222" }

This single-pixel-thick image is still big enough to encode this message.

{"255123212","001201222"}
"hi"
Returns: { "254120214",  "003200222" }

Same message, but with the second letter on a different row.

{"123234213001023213123145",
 "222111121101213198009",
 "121122123124125",
 "132212093039",
 "213110"}
"Hello 1"
Returns: { "120234212003023213122145",  "222110121102213198010",  "120120120126125",  "135215095039",  "215111" }

Notice that the image doesn't strictly need to be rectangular, letters from the message might need to wrap to multiple lines, and the whole image may not have a multiple of 3 "pixels".

{"018017024216082230021043088042086156006047121237",
 "063017015030236167097140081129247076158172075169",
 "125145181183056022052017124165227233048229019218",
 "167099209242179117064213087108145242158032161046",
 "019173050161125093121110023145062025073157039044",
 "242126210095181141068025089069238103076124214072",
 "102134208160185001154200206045121070225041155005",
 "229121179235203207141126102073043020099208161183",
 "086149131211149084211145132068112168109089239088",
 "113221052046008039175058171173030077166116203249",
 "222114220251037081215003047151190190162035062078",
 "154152063136033080197145107034116148102085083207",
 "021234047083108108253062239115246175022010131246",
 "156043049023027196194020055142011028057120209018",
 "118077003164047180187159097155038237032198026052",
 "083026101227063248008024097021138144250196021184",
 "104001186153004035080100059098134028243049130229",
 "223156252094068211051119183083060023010012013036",
 "255077122084158058187131030013123054251105096083",
 "143143236016187102049138115221043151205084229177",
 "010109089064091218237197173115204238129058190224",
 "001163070139196231145100117006124056102093104128",
 "082227197038021090058040227223030084133202147237",
 "140205195166246230025083187215004043185104167130",
 "036004051133046225010118172046177187221124129012",
 "228247138235146198145149019089041173165070215196",
 "024203003033222254207036183048084219146028216108",
 "005242064076235118224092018012245077135152116255",
 "021233175216196126052109143072166055129069217128",
 "082161078028029106082005080174119107243092164094",
 "151018051187176135144175242077140194057010057241",
 "003111110060244207054148213055089003183182217146",
 "054146183092182239154008099170234192021223224200",
 "197253114150027012167119215030188173024244180023",
 "112026124104120215088046005191164238161192238218",
 "162017082205144110163119171209081226077218039196",
 "168211003118182125085146176125209226050156255115",
 "043200116050074045093001255128180128065041212153",
 "113170120030029091015182070078056182200247167070",
 "216006053250047153206150078020008146145102181197",
 "021229094077086122175207072045012226042219061149",
 "180036184176061156136145153117205077199231250249",
 "088239120220079014244154176014227108072248210162",
 "062229235236250107198029087007254092221018045241",
 "127107243093210077108128006118244068212017129086",
 "148161212066033128195118181108107093248241147064",
 "154133208053074134226238180098141233035164227048",
 "215186026126149215073097001131080171101240207092",
 "004126144242217123017241158102208082078209222114",
 "208071210017136095130234107171052097220236198237"}
"abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWX"
Returns: { "019018025216083229021043089042087157007047121236",  "060018013028238166096142083128246076157174073169",  "126146181182059021054016126166225234050230018218",  "167098210240179118065215086110147242159035162044",  "016175049160127094120111023144063024073159037044",  "240126208092183140068024089068237101076126213072",  "103133208160186000153202204046122068227042152004",  "231120177235200206143124103075040020096209161180",  "085150128209151084209144133069113169109090237089",  "115221053044010037175059171175031079167119203251",  "223115223251039083215003047151191191163035063079",  "155155063139035083199147107035119151103087083207",  "023235047083111111255063239115247175023011131247",  "159043051023027199195023055143011031059123211019",  "119079003167047183187159099155039239035199027055",  "083027103227063251011027099023139147251199023187",  "107003187155007035083103059099135031243051131231",  "223159255095071211051119183083063023011015015039",  "255079123087159059187131031015123055251107099083",  "143143239019187103051139115223043151207087231179",  "011111091067091219239199175115207239131059191227",  "003163071139199231147103119007127059103095107131",  "083227199039023091059043227223031087135203147239",  "143207195167247231027083187215007043187107167131",  "039007051135047227011119175047179187223127131015",  "231247139235147199147151019091043175167071215199",  "027203003035223255207039183051087219147031219111",  "007243067079235119227095019015247079135155119255",  "023235175219199127055111143075167055131071219131",  "083163079031031107083007083175119107243095167095",  "151019051187179135147175243079143195059011059243",  "003111111063247207055151215055091003183183219147",  "055147183095183239155011099171235195023223227203",  "199255115151027015167119215031191175027247183023",  "115027127107123215091047007191167239163195239219",  "163019083207147111163119171211083227079219039199",  "171211003119183127087147179127211227051159255115",  "043203119051075047095003255131183131067043215155",  "115171123031031091015183071079059183203247167071",  "219007055251047155207151079023011147147103183199",  "023231095079087123175207075047015227043219063151",  "183039187179063159139147155119207079199231251251",  "091239123223079015247155179015227111075251211163",  "063231235239251107199031087007255095223019047243",  "127107243095211079111131007119247071215019131087",  "151163215067035131195119183111107095251243147067",  "155135211055075135227239183099143235035167227051",  "215187027127151215075099003131083171103243207095",  "007127147243219123019243159103211083079211223115",  "211071211019139095131235107171055099223239199239" }

{"251190015092031025240055033054024120230127087215",
 "213041224212231163241111102159167043171167113232",
 "239163090155175094064041027075249232005090207120",
 "201139204150028109028156255092031023196150226183",
 "207199120138168175229218008224130198200117081194",
 "237192025178189156038090066003044029191021018211",
 "095102121166190204083124046127070090013094104176",
 "056179145024101168177122030218120235069049081202",
 "050061182227250185231088008225137027197129231149",
 "045066084246245026196065095240209207239195032141",
 "247193179140109156172219098117246226122083137124",
 "203016079061236253052020106064120138104053102105",
 "010133058101037211105221184022138093017185196196",
 "187146007094249149074098059009181100211142240067",
 "060244199016102073230047213018202196213174229247",
 "187094146084207090175209159117165127114183035018",
 "228052030176029015118103170101051200184040108232",
 "078187222228064045149170183115080107138000251157",
 "042095052206146052196233116058233203218068159015",
 "166112046033141207030127176216244247134236066114",
 "149239077119100219213051016167171080076172103034",
 "210213223046252155009028193190156072095051009039",
 "219108095164185144089107161179003177024059108242",
 "047031104067177119152178108038239041066014096206",
 "233092177222181230049035101143184015134232104132",
 "017241153239190020187060247209063158115188084183",
 "051116190028047069054110217022125136161234196113",
 "175045031157123092120051043102222187115072033105",
 "068005084236166011069035019144231168248035114123",
 "088254069084029050150114082205174178100147178218",
 "133171250208120219137109095174153032171197004109",
 "215047243190136098132102115206240045179153088239",
 "081063140234084058000149030201183178170056005053",
 "038177242105101221132117208245089218245250193053",
 "060004031213244098075012226101155111061068149060",
 "090116107075120047021175161172097066023191052220",
 "165022034209012092175184204234190031202120065009",
 "205111171132054051153180023155211220183100008243",
 "129027189033134087102127039171244252214206026018",
 "147241033098152017066224145076162098213030096227",
 "104049121176240063036016073029210163080149018224",
 "029051161167050110055186032004248097175097035041",
 "230030022245056146224241174093105069018154147102",
 "049035230008136232001155068230133011236168052085",
 "001190184020159123223203085237048030169138088156",
 "013120083241163205053155226079021081255128236065",
 "014179064069235039253241093176059038086159134095",
 "219251239139230015089189139124095048205200213142",
 "184085241113224093053047228048167005090130009131",
 "095029177254035126014089242098020070144061161096"}
"YZ 0123456789aBcDeFgHiJkLmNoPqRsTuVwXyZ   01234689"
Returns: { "249190013094030025240052032053025123230125087215",  "213043224214231161242111102158167043170167112235",  "239161091155174095067043026073250232004089207121",  "200137204151031109030157252093028022196150224183",  "204198122138168173229218008227128199201118082195",  "236193026178188156037091066002046028189021019210",  "092101121167191206082125045125068091012094105179",  "056179146026101168176120028216120232068048081201",  "051062181227251185231088010227137026199131230151",  "045067087246247027199067095243211207239195035143",  "247195179143111159175219099119247227123083139127",  "203019079063239255055023107067123139107055103107",  "011135059103039211107223187023139095019187199199",  "187147007095251151075099059011183103211143243067",  "063247199019103075231047215019203199215175231247",  "187095147087207091175211159119167127115183035019",  "231055031179031015119103171103051203187043111235",  "079187223231067047151171183115083107139003251159",  "043095055207147055199235119059235203219071159015",  "167115047035143207031127179219247247135239067115",  "151239079119103219215051019167171083079175103035",  "211215223047255155011031195191159075095051011039",  "219111095167187147091107163179003179027059111243",  "047031107067179119155179111039239043067015099207",  "235095179223183231051035103143187015135235107135",  "019243155239191023187063247211063159115191087183",  "051119191031047071055111219023127139163235199115",  "175047031159123095123051043103223187115075035107",  "071007087239167011071035019147231171251035115123",  "091255071087031051151115083207175179103147179219",  "135171251211123219139111095175155035171199007111",  "215047243191139099135103115207243047179155091239",  "083063143235087059003151031203183179171059007055",  "039179243107103223135119211247091219247251195055",  "063007031215247099075015227103155111063071151063",  "091119107075123047023175163175099067023191055223",  "167023035211015095175187207235191031203123067011",  "207111171135055051155183023155211223183103011243",  "131027191035135087103127039171247255215207027019",  "147243035099155019067227147079163099215031099227",  "107051123179243063039019075031211163083151019227",  "031051163167051111055187035007251099175099035043",  "231031023247059147227243175095107071019155147103",  "051035231011139235003155071231135011239171055087",  "003191187023159123223203087239051031171139091159",  "015123083243163207055155227079023083255131239067",  "015179067071235039255243095179059039087159135095",  "219251239139231015091191139127095051207203215143",  "187087243115227095055047231051167007091131011131",  "095031179255035127015091243099023071147063163099" }

Submissions are judged against all 23 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class ImageSteganography with a public method vector<string> encode(vector<string> image, string message) · 23 test cases · 2 s / 256 MB per case